ISSN:
1436-4646
Keywords:
Independence system
;
bouquet of matroids
;
matroid
;
the greedy algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence systemℐ, there exist several bouquets of matroids having the same familyℐ of independent sets. We show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, whenℐ is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition ofℐ into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, we give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01589106
Permalink
