A Theory of Alternating Paths and Blossoms from the Perspective of Minimum Length

References

• [1] Ahuja RK, Magnanti TL, Orlin JB (1995) Network Flows: Theory, Algorithms and Applications (Prentice Hall, Hoboken, NJ).Google Scholar
• [2] Berge C (1957) Two theorems in graph theory. Proc. Natl. Acad. Sci. USA 43(9):842–844.Crossref, Google Scholar
• [3] Chen L, Kyng R, Liu YP, Peng R, Gutenberg MP, Sachdeva S (2022) Maximum flow and minimum-cost flow in almost-linear time. 2022 IEEE 63rd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 612–623.Google Scholar
• [4] Dinitz EA (1970) Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Doklady 11:1277–1280.Google Scholar
• [5] Echenique F, Immorlica N, Vazirani VV, eds. (2023) Online and Matching-Based Market Design (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [6] Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences (2012) Stable allocations and the practice of market design. Accessed June 24, 2020, https://www.nobelprize.org/uploads/2018/06/advanced-economicsciences2012.pdf.Google Scholar
• [7] Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. J. Res. National Bureau Standards B 69B:125–130.Crossref, Google Scholar
• [8] Edmonds J (1965) Paths, trees, and flowers. Canadian J. Math. 17(3):449–467.Crossref, Google Scholar
• [9] Even S, Kariv O (1975) An O(n2.5) algorithm for maximum matching in general graphs. 16th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Piscataway, NJ), 100–112.Google Scholar
• [10] Gabow HN (2017) The weighted matching approach to maximum cardinality matching. Fundamenta Informaticae 154(1–4):109–130.Crossref, Google Scholar
• [11] Gabow HN, Tarjan RE (1985) A linear-time algorithm for a special case of disjoint set union. J. Comput. System Sci. 30:209–221.Crossref, Google Scholar
• [12] Gabow HN, Tarjan RE (1991) Faster scaling algorithms for general graph matching problems. J. ACM 38:815–853.Crossref, Google Scholar
• [13] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• [14] Goldberg AV, Karzanov AV (2004) Maximum skew-symmetric flows and matchings. Math. Programming Ser. A 100:537–568.Crossref, Google Scholar
• [15] Hopcroft J, Karp RM (1973) An n5/2 algorithm for maximum matching in bipartite graphs. SIAM J. Comput. 2:225–231.Crossref, Google Scholar
• [16] Jerrum MR, Sinclair A (1989) Approximating the permanent. SIAM J. Comput. 18:1149–1178.Crossref, Google Scholar
• [17] Jerrum MR, Valiant LG, Vazirani VV (1986) Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43:169–188.Crossref, Google Scholar
• [18] Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. Twenty-Second Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• [19] Karzanov AV (1973) An exact estimate of an algorithm for finding a maximum flow, applied to the problem on representatives. Problems Cybernetics Seminar Combinatorial Math. (Sovetskoe Radio, Moscow), 66–70.Google Scholar
• [20] Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2:83–97.Crossref, Google Scholar
• [21] Liu YP, Sidford A (2020) Faster energy maximization for faster maximum flow. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 803–814.Google Scholar
• [22] Lovász L, Plummer MD (1986) Matching Theory (North-Holland, Amsterdam).Google Scholar
• [23] Madry A (2013) Navigating central path with electrical flows: From flows to matchings, and back. 2013 IEEE 54th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 253–262.Google Scholar
• [24] Micali S, Vazirani VV (1980) An O(VE) algorithm for finding maximum matching in general graphs. 21st Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 17–27.Google Scholar
• [25] Moulin H (2014) Cooperative Microeconomics: A Game-Theoretic Introduction, vol. 313 (Princeton University Press, Princeton, NJ).Google Scholar
• [26] Mucha M, Sankowski P (2004) Maximum matchings via Gaussian elimination. 45th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 248–255.Google Scholar
• [27] Mulmuley K, Vazirani UV, Vazirani VV (1987) Matching is as easy as matrix inversion. Combinatorica 7(1):105–113.Crossref, Google Scholar
• [28] Roth AE, Sönmez T, Ünver MU (2005) Pairwise kidney exchange. J. Econom. Theory 125(2):151–188.Crossref, Google Scholar
• [29] Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• [30] Shapley LS, Shubik M (1971) The assignment game I: The core. Internat. J. Game Theory 1(1):111–130.Crossref, Google Scholar
• [31] Tarjan RE (1975) Efficiency of a good but not linear set union algorithm. J. ACM 22:215–225.Crossref, Google Scholar
• [32] Valiant LG (1979) The complexity of computing the permanent. Theoret. Comput. Sci. 8:189–201.Crossref, Google Scholar
• [33] van den Brand J, Lee Y-T, Nanongkai D, Peng R, Saranurak T, Sidford A, Song Z, Wang D (2020) Bipartite matching in nearly-linear time on moderately dense graphs. 2020 IEEE 61st Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 919–930.Google Scholar
• [34] Vazirani VV (1994) A theory of alternating paths and blossoms for proving correctness of the O(VE) general graph maximum matching algorithm. Combinatorica 14(1):71–109.Crossref, Google Scholar
• [35] Vazirani VV (2022) The general graph matching game: Approximate core. Games Econom. Behav. 132:478–486.Crossref, Google Scholar
• [36] Wikipedia (2023) Harold W. Kuhn. Accessed August 7, 2018, https://en.wikipedia.org/wiki/Harold_W._Kuhn.Google Scholar
• [37] Wikipedia (2023) Isolation lemma. Accessed August 7, 2018, https://en.wikipedia.org/wiki/Isolation_lemma.Google Scholar