×

Greedy algorithm and symmetric matroids. (English) Zbl 0633.90089

Symmetric matroids are set systems which are obtained, in some sense, by a weakening of the structure of a matroid. These set systems are characterized by a greedy algorithm and they are suitable for dealing with autodual properties of matroids. Applications are given to the Eulerian tours of 4-regular graphs and the theory of g-matroids.

MSC:

90C35 Programming involving graphs or networks
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Bouchet, ”Isotropic systems,” to appear inEuropean Journal of Combinatorics. · Zbl 0642.05015
[2] A. Bouchet, ”Graphic presentations of isotropic systems,” submitted. · Zbl 0662.05014
[3] D. Gale, ”Optimal assignments in an ordered set: an application of matroid theory,”Journal of Combinatorial Theory 4 (1968) 176–180. · Zbl 0197.00803 · doi:10.1016/S0021-9800(68)80039-0
[4] B. Korte and D. Hausmann, ”An analysis of the greedy heuristic for independence systems,”Annals of Discrete Mathematics 2 (1978) 65–74. · Zbl 0392.90058 · doi:10.1016/S0167-5060(08)70322-4
[5] B. Korte and L. Lovàsz, ”Greedoids, a structural framework for the greedy algorithm,” in ”Progress in Combinatorial Optimization” in: W.R. Pulleyblank, ed., Proceedings of the Silver Jubilee Conference on Combinatorics, Waterloo, June 1982, (Academic Press, London/New York/San Francisco, 1984) pp. 221–243.
[6] A. Kotzig, ”Eulerian lines in finite 4-valent graphs and their transformations,” in: Erdòs and Katona, eds,Theory of Graphs., Proceedings of the Colloquium held at Tihany (Hungary), Sept. 1966 (North-Holland, Amsterdam, 1968) pp. 219–230.
[7] A. Schultze, personal communication, Oct. 1985.
[8] E. Tardòs, ”Generalized matroids,” to appear.
[9] D.J.A. Welsh,Matroid Theory (Academic Press, London, 1976).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.