Efficient algorithms for finding maximum matching in graphs

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: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: ANCLUIN, D., AND VALIANT, L. G. 1979. Fast probabilistic algorithms for Hamiltonian paths and matchings. J. Comput. Syst. Sci. 18, 144-193.
• 3: BALL, M. O., AND DERIGS, U. 1983. An analysis of alternative strategies for implementing matching algorithms. Network 13, 517-549.
• 4: BEROE, C. 1957. Two theorems in graph theory. Proc. Nat. Acad. Sci. 43, 842-844.
• 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.
• 6: COLE, R., AND HOPCROFT, J. E. 1982. On edge coloring bipartite graphs. SIAM J. Comput. 11, 540-546.
• 7: COPPERSMITH, D., AND WINOGRAD, $. 1982. On the asymptotic complexity of matrix multiplication. SIAM J. Comput. 11,472-492.
• 8: DERIGS, U. 1981. A shortest augmenting path method for solving minimal perfect matching problems. Networks II, 379-390.
• 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.
• 10: DIJKSTRA, E. W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 263-271.
• 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.
• 12: EDMONDS, J. 1965a. Path, trees and flowers. Can. J. Math. 17, 449-467.
• 13: EDMONDS, J. 1965b. Matching and a polyhedron with 0,1 vertices. J. Res. N. B. S. B, 69 (April- June), 125-130.
• 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.
• 15: EVEN, S., AND TARJAN, R. E. 1975. Network flow and testing graph connectivity. SIAM J. Comput 4, 507-518.
• 16: FORD, L. R., AND FULKERSON, D. R. 1956. Maximal flow through a network. Can. J. Math 8, 399-404.
• 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.
• 18: GABBER, O., AND GALIL, Z. 1981. Explicit construction of linear-sized superconcentrators. J. Comput. Syst. Sci. 22, 407-420.
• 19: Harold Neil Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs., 1974
• 20: Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976 [doi>10.1145/321941.321942]
• 21: GABOW, H. N. 1976b. Using Euler partitions to edge color bipartite multigraphs. Int. J. Comput. In{. Sci. 5, 344-355.
• 22: Harold N. Gabow, An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.448-456, December 1983 [doi>10.1145/800061.808776]
• 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.
• 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.
• 25: Harold N. Gabow , Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.246-251, December 1983 [doi>10.1145/800061.808753]
• 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.
• 27: GALIL, Z. 1980. An O(E2/SVS/a) algorithm for the maximal flow problem. Acta Inf. 14, 221-242.
• 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.
• 29: Zvi Galil , Silvio Micali , Harold Gabow, An O(EV log V) algorithm for finding a maximal weighted matching in general graphs, SIAM Journal on Computing, v.15 n.1, p.120-130, Feb. 1986 [doi>10.1137/0215009]
• 30: GOLDFARB, D. 1985. Efficient dual simplex algorithms for the assignment problem. Math. Program. 33, 187-203.
• 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.
• 32: HOPCROFT, J. E., AND KARP, R. M. 1973. N5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225-231.
• 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.
• 34: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 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.
• 36: KARP, R. M. 1980. An algorithm to solve the assignment problem in expected time O(mn log n). Network 10, 143-152.
• 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.
• 38: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.22-32, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22148]
• 39: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 40: KUHN, H. W. 1955. The Hungarian method for the assignment problem. Naval Res. Logist. Quart 2, 253-258.
• 41: LAWLER, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York.
• 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.
• 43: MULMULEY, K., VAZIRANi, U. V., AND VAZIRANI, V. V. 1985. Matching is as easy as matrix inversion. Manuscript, MSRI Berkeley, Berkeley, Calif.
• 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.
• 45: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 46: PLAISTED, D. A. 1984. Heuristic matching for graphs satisfying the triangle inequality. J. Algorithms 5, 163-179.
• 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.
• 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.
• 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.
• 50: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 51: TARJAN, R. E. 1977. Finding optimum branchings. Network 7, 25-35.
• 52: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 53: WEBER, G. 1981. Sensitivity analysis of optimal matchings. Networks 11, 41-56.
• 54: KAMEOA, T., AND MUNRO, I. 1974. O(}V{ ~ }El) algorithm for maximum matching of graphs. Computing 12, 91-98.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory, Verification