Journal of the ACM Bibliography
Harold N. Gabow and Robert E. Tarjan. Faster
scaling algorithms for general graph-matching problems. Journal of
the ACM, 38(4):815-853, October 1991.
[BibTeX entry]
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.
Shortcuts: