Harold N. Gabow
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 V3, where V is the number of vertices; previous implementations of Edmonds' algorithm have computation time proportional to V4. The implementation is based on a system of labels that encodes the structure of alternating paths.
- 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-602Google 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-467Google Scholar
- 5 ED~OSDS, J Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur Standards 69B (1965), 125-130Google 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 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. 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. 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. 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
Index Terms
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
Recommendations
Maximum weight induced matching in some subclasses of bipartite graphs
AbstractA subset of edges of a graph 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