New Algorithms for Maximum Weight Matching and a Decomposition Theorem

References

• Ahuja R, Magnanti T, Orlin J (1993) Network Flows: Theory, Algorithms, and Applications (Pearson, Upper Saddle River, NJ).Google Scholar
• Ahuja R, Orlin J, Stein C, Tarjan R (1994) Improved algorithms for bipartite network flow. SIAM J. Comput. 23(5):906–933.Crossref, Google Scholar
• Berge C (1958) Sur le couplage maximum d’un graphe. Comptes rendus hebdomadaires des séances de l’Académie des sciences 247:258–359.Google Scholar
• Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1997) Combinatorial Optimization (John Wiley & Sons, New York).Crossref, Google Scholar
• Cook WJ A note on matchings and separability. Discrete Appl. Math. 10(2):202–209.Google Scholar
• Cunningham W, Marsh A (1978) A primal algorithm for optimum matching. Balinski ML, Hoffman AJ, eds. Polyhedral Combinatorics—Dedicated to the Memory of D. R. Fulkerson (Springer, Berlin), 50–72.Crossref, Google Scholar
• Cygan M, Gabow H, Sankowski P (2015) Algorithmic applications of Baur-Strassen’s theorem: Shortest cycles, diameter and matchings. J. ACM 62(4):article 28.Crossref, Google Scholar
• Derigs U (1981) A shortest augmenting path method for solving minimal perfect matching problems. Networks 11(4):379–390.Crossref, Google Scholar
• Duan R, Pettie S (2014) Linear-time approximation for maximum weight matching. J. ACM 61(1):1–23.Crossref, Google Scholar
• Duan R, Pettie S, Su H-H Scaling algorithms for weighted matching in general graphs. Preprint, arXiv:1411.1919v2.Google Scholar
• Dulmage A, Mendelsohn N (1958) Coverings of bipartite graphs. Canadian J. Math. 10:517–534.Crossref, Google Scholar
• Edmonds J (1965a) Maximum matching and a polyhedron with (0, 1) vertices. J. Res. National Bureau Standards Section 69B:125–130.Crossref, Google Scholar
• Edmonds J (1965b) Paths, trees, and flowers. Canadian J. Math. 17:449–467.Crossref, Google Scholar
• Gabow H (1983) An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. Proc. 15th Annual ACM Sympos. Theory Comput., STOC (ACM, New York), 448–456.Crossref, Google Scholar
• Gabow H (1985a) A scaling algorithm for weighted matching on general graphs. Proc. 26th Annual Sympos. Foundations Comput. Sci., FOCS, (IEEE Computer Society, Washington, DC), 90–100.Crossref, Google Scholar
• Gabow H (1985b) Scaling algorithms for network problems. J. Comput. System Sci. 31:148–168.Crossref, Google Scholar
• Gabow H (1990) Data structures for weighted matching and nearest common ancestors with linking. Johnson DS, ed. Proc 1st Sympos. Discrete Algorithms, SODA ’90 (SIAM, Philadelphia), 434–443.Google Scholar
• Gabow H, Sankowski P (2013) Algebraic algorithms for b-matching, shortest undirected paths, and f-factors. Proc. 54th Sympos. Foundations Comput. Sci., FOCS ’13 (IEEE Computer Society, Washington, DC), 137–146.Crossref, Google Scholar
• Gabow H, Tarjan R (1989) Faster scaling algorithms for network problems. SIAM J. Comput. 18(5):1013–1036.Crossref, Google Scholar
• Gabow H, Tarjan R (1991) Faster scaling algorithms for general graph-matching problems. J. ACM 38(4):815–853.Crossref, Google Scholar
• Gallai T (1964) Maximale Systeme unabhängiger Kanten. Magyar Tudományos Akadémia—Matematikai Kutató Intézetének Közleményei 9:401–413.Google Scholar
• Goldberg A, Karzanov A (1995) Maximum skew-symmetric flows. Spirakis PG, ed. Proc. 3rd Eur. Sympos. Algorithms, ESA ’95 (Springer, Berlin), 155–170.Crossref, Google Scholar
• Goldberg A, Tarjan R (1987) Solving minimum-cost flow problems by successive approximation. Aho AV, ed. Proc. 9th Sympos. Theory Comput., STOC ’87 (ACM, New York), 7–18.Crossref, Google Scholar
• Goldberg A, Tarjan R (1990) Solving minimum-cost flow problems by successive approximation. Math. Oper. Res. 15(3):430–466.Link, Google Scholar
• Hoffman A, Oppenheim R (1978) Local unimodularity in the matching polytope. Ann. Discrete Math. 2:201–209.Crossref, Google Scholar
• Huang C-C, Kavitha T (2012) Efficient algorithms for maximum weight matchings in general graphs with small edge weights. Rabani Y, ed. Proc. 23rd Sympos. Discrete Algorithms SODA ’12 (SIAM, Philadelphia), 1400–1412.Crossref, Google Scholar
• Kao M-Y, Lam TW, Sung W-K, Ting H-F (2001) A decomposition theorem for maximum weight bipartite matchings. SIAM J. Comput. 31(1):18–26.Crossref, Google Scholar
• Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2:83–97.Crossref, Google Scholar
• Lawler EL (2011) Combinatorial Optimization: Networks and Matroids (Dover Publications, Mineola, NY).Google Scholar
• Le Gall F (2014) Power of tensors and fast matrix multiplication. Nabeshima K, Nagasaka K, Winkler F, Szántó , eds. Proc. 39th Internat. Sympos. Symbolic and Algebraic Comput., ISSAC ’14 (ACM, New York), 296–303.Crossref, Google Scholar
• Lee YT, Sidford A Path Finding II: An O˜(m(n)) Algorithm for the Minimum Cost Flow Problem. Preprint, arXiv: 1312.6713v2.Google Scholar
• Lovász L, Plummer M (2009) Matching Theory (AMS, Providence, RI).Crossref, Google Scholar
• Mucha M, Sankowski P (2004) Maximum matchings via Gaussian elimination. Prod. 45th Sympos. Foundations Comput. Sci., FOCS ’04 (IEEE Computer Society, Washington, DC), 248–255.Crossref, Google Scholar
• Orlin J (1988) A faster strongly polynomial minimum cost flow algorithm. Simon J, ed. Proc. 20th Sympos. Theory Comput., STOC ’88 (ACM, New York), 377–387.Crossref, Google Scholar
• Orlin J (1993) Parallel algorithms for the assignment and minimum-cost flow problems. Oper. Res. 41(2):338–350.Link, Google Scholar
• Orlin J (2013) Max flows in O(nm) time, or better. Proc. 45th Sympos. Theory Comput., STOC ’13 (ACM, New York), Vol. 41, 765–774.Crossref, Google Scholar
• Petersen J (1891) Die Theorie der regulären Graphs. Acta Mathematica 15:193–220.Crossref, Google Scholar
• Pettie S (2012) A simple reduction from maximum weight matching to maximum cardinality matching. Inform. Processing Lett. 112(23):893–898.Crossref, Google Scholar
• Schrijver A (1983) Short proofs on the matching polyhedron. J. Combinatorial Theory B 34(1):104–108.Crossref, Google Scholar
• Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, Chichester, UK).Google Scholar
• Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Tutte W (1947) The factorization of linear graphs. J. London Math. Soc. 22:107–111.Crossref, Google Scholar