Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms, networks of problems
General Terms: Algorithms, Design, Theory
Additional Key Words and Phrases: Augmenting path, blossom, matching, network optimization, scaling
Selected papers that cite this one
- Joseph Cheriyan. Randomized \tilde{O}(M(|V|)) algorithms for problems in matching theory. SIAM Journal on Computing, 26(6):1635-1655, December 1997.
- Joseph Cheriyan and Ramakrishna Thurimella. Approximating minimum-size k-connected spanning subgraphs via matching (extended abstract). In 37th Annual Symposium on Foundations of Computer Science, pages 292-301, Burlington, Vermont, 14-16 October 1996. IEEE.
- Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, April 1995.
- Kazuo Murota. Computing the degree of determinants via combinatorial relaxation. SIAM Journal on Computing, 24(4):765-796, August 1995.
Selected references
- Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248-264, April 1972.
- Harold N. Gabow. An efficient implementation of Edmonds' algorithm for maximum matching on graphs. Journal of the ACM, 23(2):221-234, April 1976.
- Harold N. Gabow. A scaling algorithm for weighted matching on general graphs. In 26th Annual Symposium on Foundations of Computer Science, pages 90-100, Portland, Oregon, 21-23 October 1985. IEEE.
- Harold N. Gabow, Zvi Galil, and Thomas H. Spencer. Efficient implementation of graph algorithms using contraction. Journal of the ACM, 36(3):540-572, July 1989.
- Silvio Micali and Vijay V. Vazirani. An O(\sqrt{|v|} \cdot |E|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, pages 17-27, Syracuse, New York, 13-15 October 1980. IEEE.
- Robert Endre Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26(4):690-715, October 1979.
- Pravin M. Vaidya. Geometry helps in matching (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 422-425, Chicago, Illinois, 2-4 May 1988.