×

zbMATH — the first resource for mathematics

Greedy algorithms and poset matroids. (English) Zbl 1308.68146
Summary: We generalize the matroid-theoretic approach to greedy algorithms to the setting of poset matroids, in the sense of M. Barnabei et al. [Adv. Appl. Math. 21, No. 1, 78–112, Art. No. AM980583 (1998; Zbl 0908.05025)]. We illustrate our result by providing a generalization of Kruskal algorithm (which finds a minimum spanning subtree of a weighted graph) to abstract simplicial complexes.

MSC:
68W05 Nonnumerical algorithms
05B35 Combinatorial aspects of matroids and geometric lattices
05E45 Combinatorial aspects of simplicial complexes
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Barnabei, M.; Nicoletti, G.; Pezzoli, L., Matroids on partially ordered sets, Adv. Appl. Math., 21, 78-112, (1998) · Zbl 0908.05025
[2] Cormen, T. H.; Leiserson, C. H.; Rivest, R. L.; Stein, C., Introduction to algorithms, (2009), MIT Press · Zbl 1187.68679
[3] Edmonds, J., Matroids and the greedy algorithm, Math. Program., 1, 127-136, (1971) · Zbl 0253.90027
[4] Faigle, U., The greedy algorithm for partially ordered sets, Discrete Math., 28, 153-159, (1979) · Zbl 0435.06003
[5] Faigle, U., Geometries on partially ordered sets, J. Comb. Theory, Ser. B, 28, 26-51, (1980) · Zbl 0359.05018
[6] Faigle, U., On ordered languages and the optimization of linear functions by greedy algorithms, J. ACM, 32, 861-870, (1985) · Zbl 0633.68016
[7] Faigle, U.; Fujishige, S., A general model for matroids and the greedy algorithm, Math. Program., Ser. A, 119, 353-369, (2009) · Zbl 1180.90268
[8] Korte, B.; Lovász, L., Mathematical structures underlying greedy algorithms, (Gecseg, F., Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, August 24-28, Lect. Notes Comput. Sci., vol. 117, (1981), Springer-Verlag Berlin), 205-209 · Zbl 0473.68019
[9] Li, Y.; Zhang, G., Rank axioms for poset greedoids, (Computational Intelligence and Security, Bejing, December 11-14, (2009)), 41-42
[10] Rado, R., A theorem on independence relations, Q. J. Math., 13, 83-89, (1942) · Zbl 0063.06369
[11] Y. Sano, The greedy algorithm for strict cg-matroids, RIMS Preprint No. 1581, Research Institute for Mathematical Sciences, Kyoto University, February 2007.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.