Constructing a perfect matching is in random NC

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constructing a perfect matching is in random NC

Full text

Pdf (934 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the seventeenth annual ACM symposium on Theory of computing table of contents

Providence, Rhode Island, United States

Pages: 22 - 32

Year of Publication: 1985

ISBN:0-89791-151-2

Authors

R M Karp	Computer Science Division, University of California at Berkeley
E Upfal	Computer Science Department, Stanford University
A Wigderson	IBM San Jose Research Laboratory

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 50, Citation Count: 5

Additional Information:

references cited by 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/22145.22148 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.

	AV	D. Angluin and L.G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and. matchings. J. of Cornp. Syst. ScL 18, (1979) pp. 155-193.
	BCP	A Borodin , S Cook , N Pippenger, Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, v.58 n.1-3, p.113-136, July/Aug./Sept. 1983 [doi>10.1016/S0019-9958(83)80060-6]
	BGH	A. Borodin, J. yon zur Gathen, and J. Hopcn~ft, F:Lst parallel matrix and GCD computations. Proc. 23d STOC (1982) pp. 65-71.
	Co	Stephen A. Cook, An overview of computational complexity, Communications of the ACM, v.26 n.6, p.400-408, June 1983 [doi>10.1145/358141.358144]
	Ed	J. Edmonds, Systems of distinct representatives and linear algebra. J. of Rex NaL Bureau ofStandardx 71A (1%7)pp. 241-245.
	EK	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	GSS	L.M. Goldschlager, R.A. Shaw and J. Staples. The maximum flow problem is Iogspace complete for P. Theoretical Computer Science 21 (1982)pp. 105-111.
	Kar	H,J. Karloff, A randomized par~dlel algorithm for the odd-set cover problem. Submitte, d, 1985.
	KUW	R M Karp , E Upfal , A Wigderson, Are search and decision programs computationally equivalent?, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.464-475, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22197]
	KVV	U Vazirani , V V Vazirani, The two-processor scheduling problem is in R-NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.11-21, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22147]
	RV	M.O. Rabin and V.V. Vazirani, Maximum match ings in general graphs through random- Mlfion. TR-15-84, Harvard University Center for Research in Computing Technology, 1984.
	Sc	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	SU	Eli Shamir , Eli Upfal, N-processors graphs distributively achieve perfect matchings in O(log2N) beats, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.238-241, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806702]
	Tu	W.T. Tutte, The factors of graphs. CanacL J. Math. 4 (1952) pp. 314-328.
	We	D,J.A. Welsh, Matroid Theory. Academic Press (1976).

CITED BY 5

	R M Karp , E Upfal , A Wigderson, Are search and decision programs computationally equivalent?, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.464-475, May 06-08, 1985, Providence, Rhode Island, United States
	Baruch Shieber , Shlomo Moran, Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: maximum matchings, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.282-292, August 11-13, 1986, Calgary, Alberta, Canada
	Zvi Galil, Efficient algorithms for finding maximum matching in graphs, ACM Computing Surveys (CSUR), v.18 n.1, p.23-38, March 1986
	Zvi Lotker , Boaz Patt-Shamir , Seth Pettie, Improved distributed approximate matching, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Zvi Lotker , Boaz Patt-Shamir , Adi Rosen, Distributed approximate matching, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA