An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- 1 April 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (2), 221-234
- https://doi.org/10.1145/321941.321942
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 3 , where V is the number of vertices; previous implementations of Edmonds' algorithm have computation time proportional to V 4 . The implementation is based on a system of labels that encodes the structure of alternating paths.Keywords
This publication has 7 references indexed in Scilit:
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Optimal scheduling for two-processor systemsActa Informatica, 1972
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- Optimal Sequencing of Two Equivalent ProcessorsSIAM Journal on Applied Mathematics, 1969
- Modification of Edmonds' maximum matching algorithmJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965
- TWO THEOREMS IN GRAPH THEORYProceedings of the National Academy of Sciences of the United States of America, 1957