The Weighted Matching Approach to Maximum Cardinality Matching

• Autorzy: Gabow H. N.

Identyfikatory

DOI

10.3233/FI-2017-1555

• Języki publikacji: EN

Abstrakty

EN

Several papers have achieved time O(√nm) for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds’ algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time O(√nm).

Słowa kluczowe

EN

weighted graph; cardinal numbers; algorithms; variables; linear models

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 109--130
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Gabow H. N.

• Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado 80309-0430, USA

Bibliografia

• [1] Micali S, Vazirani VV. An O(√׀v׀∙׀E׀) algorithm for finding maximum matching in general graphs. In: Proc. 21st Annual Symp. on Found. of Comp. Sci. 1980 pp. 17–27. doi:10.1109/SFCS.1980.12 .
• [2] Vazirani VV. A theory of alternating paths and blossoms for proving correctness of the O(√V E) general graph maximum matching algorithm. Combinatorica, 1994;14(1):71–109.
• [3] Vazirani VV. A simplification of the MV matching algorithm and its proof. CoRR, abs/1210.4594v5. Also “A proof of the MV matching algorithm”, manuscript, May 13, 2014, 42 pages.
• [4] Gabow HN, Tarjan RE. Faster scaling algorithms for general graph matching problems. J. ACM, 1991;38(4):815–853. doi:10.1145/115234.115366.
• [5] Edmonds J. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Standards, 1965;69B:125–130. URL https://www.bibsonomy.org/bibtex/2a3a3ef104190926e124d4126d2bfc919/ytyoun.
• [6] Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A. Combinatorial Optimization. Wiley and Sons, New York, 1998. ISBN-10:0486402584, 13:978-0486402581.
• [7] Lawler EL. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976. ISBN-0486414531, 9780486414539.
• [8] Papadimitriou CH, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1982. ISBN-0486402584, 9780486402581.
• [9] Schrijver A. Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York, 2003. ISBN-10:3540443894, 13:978-3540443896.
• [10] Hopcroft JE, Karp RM. An n2.5 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 1973;2(4):225–231. URL https://doi.org/10.1137/0202019.
• [11] Karzanov AV. On finding maximum flows in network with special structure and some applications. Math. Problems for Production Control. Moscow State University Press, Moscow 1976;5:81–94.
• [12] Goldberg AV, Karzanov AV. Maximum skew-symmetric flows and matchings. Math. Program., Series A. 2004;100(3):537–568. doi:10.1007/s10107-004-0505-z.
• [13] Gabow HN, Tarjan RE. A linear–time algorithm for a special case of disjoint set union. J. Comp. And System Sci., 1985;30(2):209–221. URL https://doi.org/10.1016/0022-0000(85)90014-5.