×

zbMATH — the first resource for mathematics

An analysis of alternative strategies for implementing matching algorithms. (English) Zbl 0519.68055

MSC:
68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] , and , The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).
[2] A linear-time algorithm for finding a minimum-weight spanning tree in graphs in which all cycles pass through a single vertex. Unpublished.
[3] and , A computational study comparing the efficiency of various list structures in matching algorithm. Unpublished.
[4] Ball, Transportation Sci. 17 pp 4– (1983)
[5] Cunningham, Math. Programming Study 8 pp 50– (1976) · doi:10.1007/BFb0121194
[6] Derigs, Networks 11 pp 379– (1981)
[7] Matching code theory part I: Combinatorial structures and the cardinality matching problem. Working Paper MS/S No. 81–041, College of Business and Management, University of Maryland at College Park (1981).
[8] Shortest augmenting paths and sensitivity analysis for optimal matchings. Report 82222-OR, Institut für Ökonometrie und Operations Research, Universität Bonn (1982).
[9] and , On two methods for solving minimal perfect matching problems. In Proceedings of the Second Danish/Polish Mathematical Programming Seminar, J. Krarup and S. Walukiewicz, Eds. (1980), pp. 85–100.
[10] Edmonds, J. Res. Natl. Bur. Standards 69B pp 125– (1965) · Zbl 0141.21802 · doi:10.6028/jres.069B.013
[11] and , Facets of 1-matching polyhedra. In Hypergraph Seminar, Lecture Notes in Mathematics 411 (1974) 214–242.
[12] , and , Priority queries with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs. Unpublished manuscript (1982).
[13] Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976), pp. 217–263.
[14] Nemhauser, Naval Res. Logist. Quart. 26 pp 553– (1979) · Zbl 0496.90057 · doi:10.1002/nav.3800260401
[15] and , Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ (1976).
[16] Faces of matching polyhedra. Thesis, University of Waterloo, 1973.
[17] Weber, Networks 11 pp 41– (1981)
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.