article

Free access

An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

Author:

Harold N. GabowAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 2

Pages 221 - 234

https://doi.org/10.1145/321941.321942

Published: 01 April 1976 Publication History

PDF eReader

Abstract

A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding a maximum matching. The computation time is proportional to V³, where V is the number of vertices; previous implementations of Edmonds' algorithm have computation time proportional to V⁴. The implementation is based on a system of labels that encodes the structure of alternating paths.

References

[1]

BALINSKI, M.L. Labelling to obtain a maximum matching In Comb,natomal Mathematics and Its Appl, eations, R.C. Bose and T.A Dowling, Eds, U. of North Carolina Press, Chapel Hill, N.C., 1967, pp. 585-602

Google Scholar

[2]

BERGE, C. Two theorems in graph theory. Proc. Nat. Acad. Sc~. $8 (1957), 842-844.

Google Scholar

[3]

COFFMAN, E J. JR., AND GRAHAM, R L Optimal scheduling for two-processor systems. Acta Informatica I (1972), 200--213.

Google Scholar

[4]

EDMONDS, j. Paths, trees and flowers. Canad J. Math. 17 (1965), 449-467

Google Scholar

[5]

ED~OSDS, J Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur Standards 69B (1965), 125-130

Google Scholar

[6]

FuJH, M., KASAM~, T., AND N}NOMIVA, K. Optimal sequencing of two equivalent processors. SIAM J. Applied Math. 17 (1969), 784-789; Erratum, 20 (1971), 141.

Google Scholar

[7]

GABOW, H. An efficient implementation of Edmonds' maximum matching algorithm Tech. Rep. 328, Comput. Sci. Dep, Stanford U., Stanford, Cahf, 1972

Crossref

Google Scholar

[8]

GAvow, H. Implementations of algorithms for maximum matching on nonbipartite graphs. Ph.D. diss., Comput. Sci. Dep., Stanford U., Stanford, Cahf., 1973.

Crossref

Google Scholar

[9]

HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.

Google Scholar

[10]

KNVTH, D The Art of Computer Programming, Vol. I. Addison-Wesley, Reading Mass, 1968.

Crossref

Google Scholar

[11]

TARJAN, R.E. An efficient planarity algorithm. Tech. Rep. 244, Comput. Sci. Dep., Stanford U., Stanford, Calif., 1971.

Google Scholar

[12]

TARJAN, R.E. Efficiency of a good but not linear set union algorithm. J. ACM $2, 2 (April 1975), 215-225.

Crossref

Google Scholar

[13]

WITZGALL, D., AND ZAHN, C T. JR. Modification of Edmonds' algorithm for maximum matching of graphs. J. Res. Nat. Bur. Standards 69B (1965), 91-98.

Google Scholar

Cited By

View all

Mišura AVukičević DPerić Hadžić A(2024)The Optimal Arrangement of Boats in a Coastal Maritime Passenger Lines System Using Graph TheorySustainability10.3390/su1622996116:22(9961)Online publication date: 15-Nov-2024
https://doi.org/10.3390/su16229961
Aziz HCsáji GCseh A(2024)Computational complexity of k-stable matchingsACM Transactions on Economics and Computation10.1145/3708507Online publication date: 13-Dec-2024
https://dl.acm.org/doi/10.1145/3708507
Choe SKönig R(2024)Long-range data transmission in a fault-tolerant quantum bus architecturenpj Quantum Information10.1038/s41534-024-00928-410:1Online publication date: 26-Dec-2024
https://doi.org/10.1038/s41534-024-00928-4
Show More Cited By

Index Terms

An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

An efficient implementation of Edmonds'' maximum matching algorithm.
Maximum weight induced matching in some subclasses of bipartite graphs
Abstract
A subset $M \subseteq E$ of edges of a graph $G = (V, E)$ is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is the same as G[S], the subgraph of G induced ...
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 ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 23, Issue 2

April 1976

176 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321941

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1976

Published in JACM Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

281
Total Citations
View Citations
3,557
Total Downloads

Downloads (Last 12 months)166
Downloads (Last 6 weeks)22

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mišura AVukičević DPerić Hadžić A(2024)The Optimal Arrangement of Boats in a Coastal Maritime Passenger Lines System Using Graph TheorySustainability10.3390/su1622996116:22(9961)Online publication date: 15-Nov-2024
https://doi.org/10.3390/su16229961
Aziz HCsáji GCseh A(2024)Computational complexity of k-stable matchingsACM Transactions on Economics and Computation10.1145/3708507Online publication date: 13-Dec-2024
https://dl.acm.org/doi/10.1145/3708507
Choe SKönig R(2024)Long-range data transmission in a fault-tolerant quantum bus architecturenpj Quantum Information10.1038/s41534-024-00928-410:1Online publication date: 26-Dec-2024
https://doi.org/10.1038/s41534-024-00928-4
Du RZhang MZhang NLiu YDong GTian LKong ZAhsan M(2024)Evaluation of key node groups of embodied carbon emission transfer network in China based on complex network control theoryJournal of Cleaner Production10.1016/j.jclepro.2024.141605(141605)Online publication date: Mar-2024
https://doi.org/10.1016/j.jclepro.2024.141605
Li YGe YXu TZhu MHe Z(2024)Controllability evaluation of complex networks in cyber–physical power systems via critical nodes and edgesInternational Journal of Electrical Power & Energy Systems10.1016/j.ijepes.2023.109625155(109625)Online publication date: Jan-2024
https://doi.org/10.1016/j.ijepes.2023.109625
Lee TLu BChu H(2023)A DFS Algorithm for Maximum Matchings in General GraphsNatural Language Processing, Information Retrieval and AI10.5121/csit.2023.130310(115-129)Online publication date: 18-Feb-2023
https://doi.org/10.5121/csit.2023.130310
Sahebolamri ABarrett LMoore SMicinski K(2023)Bring Your Own Data Structures to DatalogProceedings of the ACM on Programming Languages10.1145/36228407:OOPSLA2(1198-1223)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622840
Subramani KWojciechowski P(2023)Constrained read-once refutations in UTVPI constraint systems: A parallel perspectiveMathematical Structures in Computer Science10.1017/S0960129523000300(1-17)Online publication date: 11-Sep-2023
https://doi.org/10.1017/S0960129523000300
Wang NLyu YJia SZheng CMeng ZChen J(2023)A dynamic graph-based many-to-one ride-matching approach for shared autonomous electric vehiclesTransportation10.1007/s11116-023-10391-351:5(1879-1905)Online publication date: 15-Apr-2023
https://doi.org/10.1007/s11116-023-10391-3
Gabow H(2023)A Weight-Scaling Algorithm for f-Factors of MultigraphsAlgorithmica10.1007/s00453-023-01127-x85:10(3214-3289)Online publication date: 18-May-2023
https://dl.acm.org/doi/10.1007/s00453-023-01127-x
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

Index Terms

Recommendations

An efficient implementation of Edmonds'' maximum matching algorithm.

Maximum weight induced matching in some subclasses of bipartite 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

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