article

Free access

Efficient algorithms for finding maximum matching in graphs

Author:

Zvi GalilAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 18, Issue 1

Pages 23 - 38

https://doi.org/10.1145/6462.6502

Published: 01 March 1986 Publication History

PDF eReader

Abstract

This paper surveys the techniques used for designing the most efficient algorithms for finding a maximum cardinality or weighted matching in (general or bipartite) graphs. It also lists some open problems concerning possible improvements in existing algorithms and the existence of fast parallel algorithms for these problems.

References

[1]

AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.

Crossref

Google Scholar

[2]

ANCLUIN, D., AND VALIANT, L. G. 1979. Fast probabilistic algorithms for Hamiltonian paths and matchings. J. Comput. Syst. Sci. 18, 144-193.

Google Scholar

[3]

BALL, M. O., AND DERIGS, U. 1983. An analysis of alternative strategies for implementing matching algorithms. Network 13, 517-549.

Google Scholar

[4]

BEROE, C. 1957. Two theorems in graph theory. Proc. Nat. Acad. Sci. 43, 842-844.

Google Scholar

[5]

BORODIN, A., VON ZUR GATHEN, J., AND HOPCROFT, J. E. 1982. Fast parallel and gcd computations. In Proceedings o{ the 23rd Annual IEEE Symposlum on Foundations of Computer Science. IEEE, New York, pp. 64-71.

Google Scholar

[6]

COLE, R., AND HOPCROFT, J. E. 1982. On edge coloring bipartite graphs. SIAM J. Comput. 11, 540-546.

Google Scholar

[7]

COPPERSMITH, D., AND WINOGRAD, $. 1982. On the asymptotic complexity of matrix multiplication. SIAM J. Comput. 11,472-492.

Google Scholar

[8]

DERIGS, U. 1981. A shortest augmenting path method for solving minimal perfect matching problems. Networks II, 379-390.

Google Scholar

[9]

DERIGS, U. 1982. Shortest augmenting paths and sensitivity analysis for optimal matchings. Rep. 82222-OR, Institut f/Jr Okonometrie und Operations Research, Univ. Bonn, West Germany, April.

Google Scholar

[10]

DIJKSTRA, E. W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 263-271.

Google Scholar

[11]

DINIC, E. A. 1970. Algorithm for solution of a problem of maximal flow in a network with power estimation. Sov. Math. Dokl. 11, 1277-1280.

Google Scholar

[12]

EDMONDS, J. 1965a. Path, trees and flowers. Can. J. Math. 17, 449-467.

Google Scholar

[13]

EDMONDS, J. 1965b. Matching and a polyhedron with 0,1 vertices. J. Res. N. B. S. B, 69 (April- June), 125-130.

Google Scholar

[14]

EVEN, S., AND KAR!V, O. 1975. An O(n2'5) algorithm for maximum matching in graphs. In Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 100-112.

Google Scholar

[15]

EVEN, S., AND TARJAN, R. E. 1975. Network flow and testing graph connectivity. SIAM J. Comput 4, 507-518.

Google Scholar

[16]

FORD, L. R., AND FULKERSON, D. R. 1956. Maximal flow through a network. Can. J. Math 8, 399-404.

Google Scholar

[17]

FREOMAN, M. L., AND TARJAN, R. E. 1984. Fibonacci heaps and their uses (in improved network optimization algorithms). In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 338-346.

Google Scholar

[18]

GABBER, O., AND GALIL, Z. 1981. Explicit construction of linear-sized superconcentrators. J. Comput. Syst. Sci. 22, 407-420.

Google Scholar

[19]

GABOW, H. N. 1974. Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. dissertation, Dept. of Computer Science, Stanford Univ., Stanford, Calif.

Crossref

Google Scholar

[20]

GABOW, H. N. 1976a. An efficient implementation of Edmonds' algorithm for maximum matching on graphs. J. ACM 23, 2 (Apr.), 221-234.

Crossref

Google Scholar

[21]

GABOW, H. N. 1976b. Using Euler partitions to edge color bipartite multigraphs. Int. J. Comput. In{. Sci. 5, 344-355.

Google Scholar

[22]

GABOW, H. N. 1983a. An efficient reduction technique for degree-constrained subgraphs and bidirected network flow problems. In Proceedings of the 15th Annual A CM Symposium on Theory of Computing (Boston, Apr. 25-27). ACM, New York, pp. 448-456.

Crossref

Google Scholar

[23]

GABOW, H. N. 1983b. Scaling algorithms for network problems. In Proceedings of the 24th Annual IEEE Symposium on Foundations o{ Computer Science. IEEE, New York, pp. 248-257.

Google Scholar

[24]

GABOW, H. N. 1985. A scaling algorithm for weighted matching on general graphs. In Proceedings o{ the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 90-100.

Google Scholar

[25]

GABOW, H. N., AND TARJAN. R. E. 1983. A linear time algorithm for a special case of disjoint set union. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (Boston, Apr. 25-27). ACM, New York, pp. 246-251.

Crossref

Google Scholar

[26]

GABOW, H. N., GALIL, Z., AND SPENCER, T. H. 1984. Efficient implementation of graph algorithms using contraction. In Proceedings o{ the 25th Annual IEEE Symposium on Foundations o{ Computer Science. IEEE, New York, pp. 347-357.

Google Scholar

[27]

GALIL, Z. 1980. An O(E2/SVS/a) algorithm for the maximal flow problem. Acta Inf. 14, 221-242.

Google Scholar

[28]

GALIL, Z., AND PAN, V. 1985. Improved processor bounds for algebraic and combinatorial problems in RNC. in Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 490-495.

Google Scholar

[29]

GALIL, Z., MICAL!, S., AND GABOW, H. N. 1986. An O(EV log V) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15, 120-130.

Crossref

Google Scholar

[30]

GOLDFARB, D. 1985. Efficient dual simplex algorithms for the assignment problem. Math. Program. 33, 187-203.

Google Scholar

[31]

GOLDSCHLAGER, L., SHAW, R., AND STAPLES, J. 1982. The maximum flow problem is log space complete for P. Theor. Comput. Sci. 21,105-111.

Google Scholar

[32]

HOPCROFT, J. E., AND KARP, R. M. 1973. N5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225-231.

Google Scholar

[33]

IRI, M., MUROTA, K., ANO MATSUI, S. 1981. Linear time approximation algorithms for finding the minimum weight perfect matching on a plan. Inf. Process. Lett. 12, 206-209.

Google Scholar

[34]

JOHNSON, D. 1977. Efficient algorithms for shortest paths in sparse networks. J. ACM 24, i (Jan.), 1-13.

Crossref

Google Scholar

[35]

KARIV, O. 1976. An O(nz~) algorithm for maximal matching in general graphs. Ph.D. dissertation, Dept. of Applied Mathematics, The Weizmann Institute, Rehovot, Israel.

Google Scholar

[36]

KARP, R. M. 1980. An algorithm to solve the assignment problem in expected time O(mn log n). Network 10, 143-152.

Google Scholar

[37]

KARP, R. M., AND SIPSER, M. 1981. Maximal matchings in sparse graphs. In Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science. iEEE, New York, pp. 364-375.

Google Scholar

[38]

KARP, R. M., UPFAL, E., AND WIGOERSON, A. 1985. Constructing a perfect matching is in random NC. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, pp. 22-32.

Crossref

Google Scholar

[39]

KNUTH, D. E. 1973. The Art o{ Computer Programming. Vol. 3, Sorting and Searching. Addison- Wesley, Reading, Mass.

Crossref

Google Scholar

[40]

KUHN, H. W. 1955. The Hungarian method for the assignment problem. Naval Res. Logist. Quart 2, 253-258.

Google Scholar

[41]

LAWLER, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York.

Google Scholar

[42]

MICALI, S., AND VAZmANi, V. V. 1980. An of value algorithm for finding maximal matching in general graphs. In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 17-27.

Google Scholar

[43]

MULMULEY, K., VAZIRANi, U. V., AND VAZIRANI, V. V. 1985. Matching is as easy as matrix inversion. Manuscript, MSRI Berkeley, Berkeley, Calif.

Google Scholar

[44]

NORMAN, R. Z., AND RABIN, M. O. 1959. An algorithm for a minimum cover of a graph. Proc. Am. Math. Soc. I0, 315-319.

Google Scholar

[45]

PAPADIMITRIOU, C. H., AND STEIGLITZ, $. 1982. Combinatorial Optimization, Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, N.J.

Crossref

Google Scholar

[46]

PLAISTED, D. A. 1984. Heuristic matching for graphs satisfying the triangle inequality. J. Algorithms 5, 163-179.

Google Scholar

[47]

RABIN, M. O., AND VAZIRAN!, V. V. 1984. Maximum matchings in general graphs through randomization. Rep. TR-15-84, Center for Research in Computing Technology, Harvard Univ., Cambridge, Mass., Oct.

Google Scholar

[48]

SLISENKO, A. O. 1973. Recognition of palindromes by multihead Turing machines. In Problems in the Constructive Trend in Mathematics. VI. In Proceedings of the Steklov Institute o{ Mathematics, vol. 129, V. P. Orevkov and N. A. Sanin, Eds. Academy of Sciences of the U.S.S.R., pp. 30-202; R. H. Silverman, Trans. Am. Math. Soc. (1976), 25-2O8.

Google Scholar

[49]

STOCKMEYER, L. J., AND V^ZIR^NI, V. V. 1982. NP- completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15, 11-19.

Google Scholar

[50]

TARJAN, R. E. 1975. Efficiency of a good but not linear set union algorithm, d. ACM 22, 2 (Apr.), 215-225.

Crossref

Google Scholar

[51]

TARJAN, R. E. 1977. Finding optimum branchings. Network 7, 25-35.

Google Scholar

[52]

TARJAN, R. E. 1983. Data structures and network algorithms. SIAM, publications.

Crossref

Google Scholar

[53]

WEBER, G. 1981. Sensitivity analysis of optimal matchings. Networks 11, 41-56.

Google Scholar

[54]

KAMEOA, T., AND MUNRO, I. 1974. O(}V{ ~ }El) algorithm for maximum matching of graphs. Computing 12, 91-98.

Google Scholar

Cited By

View all

Strzoda AGrochla K(2024)A Nature-Inspired Approach to Energy-Efficient Relay Selection in Low-Power Wide-Area Networks (LPWAN)Sensors10.3390/s2411334824:11(3348)Online publication date: 23-May-2024
https://doi.org/10.3390/s24113348
Shi BLi SLuo YZhu L(2024)Truthful mechanisms to maximize the social welfare in real-time ride-sharingWeb Intelligence10.3233/WEB-23040122:1(65-82)Online publication date: 26-Mar-2024
https://doi.org/10.3233/WEB-230401
Paschalidis PZhang RLi N(2024)Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis2024 American Control Conference (ACC)10.23919/ACC60939.2024.10644845(4044-4049)Online publication date: 10-Jul-2024
https://doi.org/10.23919/ACC60939.2024.10644845
Show More Cited By

Recommendations

Finding a maximum induced matching in weakly chordal graphs
Special issue: The 18th British combinatorial conference

An induced matching in a graph G is a set of edges, no two of which meet a common vertex or are joined by an edge of G; that is, an induced matching is a matching which forms an induced subgraph. It is known that finding an induced matching of maximum ...
Finding Maximum Induced Matchings in Subclasses of Claw-Free and P5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size

In a graph G a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of G. The maximum induced matching (abbreviated MIM) problem is to find the maximum size ...
Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs

We introduce a new framework for restricted 2-matchings close to Hamilton cycles. For an undirected graph(V,E) and a familyU of vertex subsets, a 2-matchingF is called U-feasible if |F[U]||U|1 for each UU, where F[U] is the set of edges in F induced by ...

Reviews

Reviewer: Christoph M. Hoffmann

Four matching problems and their algorithmic solutions are surveyed. The survey is intended to provide a case study for good algorithm design. The four problems considered are as follows: (1)finding a matching of maximum cardinality in bipartite graphs, (2)finding a matching of maximum cardinality in general graphs, (3)finding a matching of maximum weight in bipartite graphs, and (4)finding a matching of maximum weight in general graphs. In problems (3) and (4), each graph edge has an assigned weight. Thus, unweighted graphs are simply the special case of assigning weight 1 to every edge. The problems are discussed in order, from the easiest (1) to the hardest (4). The survey is lucid and readable. Only sequential algorithms for the problems are discussed in depth, although pointers to the literature are given for parallel and randomized solutions. Because of the publication delay of this survey, work appearing after 1982 is only very briefly surveyed.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM Computing Surveys Volume 18, Issue 1

March 1986

103 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/6462

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1986

Published in CSUR Volume 18, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

366
Total Citations
View Citations
10,218
Total Downloads

Downloads (Last 12 months)776
Downloads (Last 6 weeks)118

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Strzoda AGrochla K(2024)A Nature-Inspired Approach to Energy-Efficient Relay Selection in Low-Power Wide-Area Networks (LPWAN)Sensors10.3390/s2411334824:11(3348)Online publication date: 23-May-2024
https://doi.org/10.3390/s24113348
Shi BLi SLuo YZhu L(2024)Truthful mechanisms to maximize the social welfare in real-time ride-sharingWeb Intelligence10.3233/WEB-23040122:1(65-82)Online publication date: 26-Mar-2024
https://doi.org/10.3233/WEB-230401
Paschalidis PZhang RLi N(2024)Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis2024 American Control Conference (ACC)10.23919/ACC60939.2024.10644845(4044-4049)Online publication date: 10-Jul-2024
https://doi.org/10.23919/ACC60939.2024.10644845
Feng YCaldentey RXin LZhong YWang BHu H(2024)Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation ManagementManagement Science10.1287/mnsc.2022.01588Online publication date: 19-Mar-2024
https://doi.org/10.1287/mnsc.2022.01588
Al-Hossami EBunescu RSmith JTeehan RStephenson BStone JBattestilli LRebelsky SShoop L(2024)Can Language Models Employ the Socratic Method? Experiments with Code DebuggingProceedings of the 55th ACM Technical Symposium on Computer Science Education V. 110.1145/3626252.3630799(53-59)Online publication date: 7-Mar-2024
https://dl.acm.org/doi/10.1145/3626252.3630799
Nie WCai SZhao ZLi ZZhou TZhang Y(2024)Investigating the min‐cost minimum fleet problem through taxi data analysisComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1310639:6(929-940)Online publication date: 8-Mar-2024
https://dl.acm.org/doi/10.1111/mice.13106
Bhavsar TJindal A(2024)Cooperative NOMA Aided Improved Connectivity in Downlink Through Smart User Pairing2024 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)10.1109/PACRIM61180.2024.10690204(1-7)Online publication date: 21-Aug-2024
https://doi.org/10.1109/PACRIM61180.2024.10690204
Tong HMinku LMenzel SSendhoff BYao X(2024)Evaluating Meta-Heuristic Algorithms for Dynamic Capacitated Arc Routing Problems Based on a Novel Lower Bound MethodIEEE Computational Intelligence Magazine10.1109/MCI.2024.344021319:4(31-44)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/MCI.2024.3440213
İşler DCabana EGarcia–Recuero AKoutrika GLaoutaris N(2024)FreqyWM: Frequency Watermarking for the New Data Economy2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00379(4993-5007)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00379
Wang SJiang YChe LWang RLi S(2024)Enhancing insights into diseases through horizontal gene transfer event detection from gut microbiomeNucleic Acids Research10.1093/nar/gkae51552:14(e61-e61)Online publication date: 17-Jun-2024
https://doi.org/10.1093/nar/gkae515
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Finding a maximum induced matching in weakly chordal graphs

Finding Maximum Induced Matchings in Subclasses of Claw-Free and P5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size

Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations