Unique maximum matching algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Unique maximum matching algorithms

Full text

Pdf (813 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 70 - 78

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Harold N. Gabow	Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado
Haim Kaplan	AT&T Labs Research, Florham Park, NJ
Robert E. Tarjan	Department of Computer Science, Princeton University, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 78, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301273 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M.O. Ball and U. Derigs. An analysis of alternative strategies for implementing matching algorithms. Networks, 13:517-549, 1983,
	2	Therese C. Biedl , Prosenjit Bose , Erik D. Demaine , Anna Lubiw, Efficient algorithms for Petersen's matching theorem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.130-139, January 17-19, 1999, Baltimore, Maryland, United States
	3	R.B. Carey and G.D. Stormo. Graph-theoretic approach to RNA modeling using comparative data. In Proceedings 3rd International Conf. on Intelligent Systems for Molecular Biology, pages 75-80, t995.
	4	J. Edmonds. Maximum matching and a polyhedron with 0,l-vertices. J. Res. Nat. Bur. Standards, 69B: I25-130, 1965.
	5	J. Edmonds. Paths, trees, and flowers. Canadian d. Math, pages 233-240, 1965.
	6	H. N. Gabow. Algorithmic proofs of two relations between connectivity and the l-factors of a graph. Discrete Math, 26:33-40, 1979.
	7	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]
	8	H. N. Gabow and R. E. Tarjan. A linear time al~ gorithm for a special case of disjoint set union. J. Computer and System Sciences, 30:209-221, 1985.
	9	Harold N. Gablow , Robert E. Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM (JACM), v.38 n.4, p.815-853, Oct. 1991 [doi>10.1145/115234.115366]
	10	H.N. Oabow. A scaling algorithm for weighted matching on general graphs. In Proc. 261h Annual Syrup. on Found. of Comp. Sci., pages 90-100, 1985.
	11	Harold N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 22-24, 1990, San Francisco, California, United States
	12	M. C. Golumbic, T. Hirst, and M. Lewenstein. Uniquely restricted matchings, manuscript, 1998.
	13	Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.79-89, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276715]
	14	A. Kotzig. On the theory of finite graphs with a linear factor I. Mat.-Fyz. ~asopis Slovensk. Akad. Vied, 9:73-91, 1959.
	15	E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart and Winston, New York, 1976.
	16	L. Lov&sz and M.D. Plummet. Matching Theory. North-Holland, Amsterdam, 1986.
	17	i.E. Tabaska, R.B. Gary, H.N. Gabow, and G.D. Stormo. An RNA folding method capable of identifying pseudoknots and base triples. Bioinformatics, 14($):691~99, m9S.
	18	R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Computing, 1:146--160, 1972.
	19	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	20	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]
	21	M. Thorup. Private communication, 1998.
	22	Mikkel Thorup, Decremental dynamic connectivity, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.305-313, January 05-07, 1997, New Orleans, Louisiana, United States