Journal of the ACM · 1976 · 340 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationGraph AlgorithmsGraph LabelingMatching TheoryGraph MatchingMatchingMatching AlgorithmsMatching Problems
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.
9
Jack Edmonds · Canadian Journal of Mathematics · 1965 · 2.4K citations · Full text
Optimal scheduling for two-processor systems
E. G. Coffman, Ronald Graham · Acta Informatica · 1972 · 610 citations
Claude Berge · Proceedings of the National Academy of Sciences · 1957 · 574 citations · Full text
Implementation of algorithms for maximum matching on nonbipartite graphs.
Harold N. Gabow · 1974 · 200 citations