Fast connected components algorithms for the EREW PRAM

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast connected components algorithms for the EREW PRAM

Full text

Pdf (879 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, United States

Pages: 373 - 381

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

David R. Karger
Noam Nisan
Michal Parnas

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 40, Citation Count: 11

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/140901.141920 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.

	AKL*79	R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, and C. Rackoff. Random walks, universal sequences and the con~plexity of maze problems. In 20th Annual ,Symposium on Foundotions of Computer Science, San Juan, Pverto Rzco, 1979.
	AS87	B. Awerbuch , Y. Shiloach, New connectivity and MSF algorithms for shuffle-exchange network and PRAM, IEEE Transactions on Computers, v.36 n.10, p.1258-1263, Oct. 1987 [doi>10.1109/TC.1987.1676869]
	BR91	Greg Barnes , Walter L. Ruzzo, Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space., Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.43-53, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103430]
	C88	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	CDR86	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	CLC82	Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
	CV86	R.Cole and U.Vishin. Approximate and Exact, Parallel Scheduling with Applications to List,, Tree and Graph Problems. Proc. 27th Annual Symposium on Foundations of Computer Science, 1985.
	DKR90	M. Dietzfelbinger , M. Kutylowski , R. Reischuk, Exact time bounds for computing boolean functions on PRAMs without simultaneous writes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.125-135, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97678]
	Gaz86	H.Gazit. An Optimal Ra.ndomized Parallel Algorithm for Finding connect, ed Components in a Graph. Proc. 27th Annual Symposium on Foundations of Computer Science, 1986.
	HCS79	D. S. Hirschberg , A. K. Chandra , D. V. Sarwate, Computing connected components on parallel computers, Communications of the ACM, v.22 n.8, p.461-464, Aug. 1979 [doi>10.1145/359138.359141]
	JM91	Donald B. Johnson , Panagiotis Metaxas, Connected components in O(lg3/2\|V\|) parallel time for the CREW PRAM (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.688-697, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185437]
	KR90	R.M. I(a.rp and V. Ramachandran. Parallel Algorithms for Shared-Memory Machines. In Handbook of Theoretical Computer Science, Vol A, J. van Leeuwen Ed., 869-932, 1990.
	L	N.LiniaI. Personal Communication.
	N90a	N. Nisan. 1-way vs. 2-way access to randomness in Logspace. Proc. 5th IEEE Structure in Complexity Theory Conf., Barcelona, 1990.
	N90b	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	NSW92	N.Nisan, E.Szemeredi and A. Wigderson. Undirected Connectivity in O(logl's n) Space. Manuscrtpt.
	SV82	Y.Shitoach and U.Vishkin. An O(log n) Parallel Connectivity Algorithm. Journal of Algorithms 3:57-67, 1982.

CITED BY 11

	Ka Wong Chong , Tak Wah Lam, Finding connected components in O(log n loglog n) time on the EREW PRAM, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.11-20, January 25-27, 1993, Austin, Texas, United States
	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	Greg Barnes , Uriel Feige, Short random walks on graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.728-737, May 16-18, 1993, San Diego, California, United States
	Ka Wong Chong , Yijie Han , Tak Wah Lam, Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM (JACM), v.48 n.2, p.297-323, March 2001
	Steven S. Lumetta , Arvind Krishnamurthy , David E. Culler, Towards modeling the performance of a fast connected components algorithm on parallel machines, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, December 04-08, 1995, San Diego, California, United States
	Shay Halperin , Uri Zwick, Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.438-447, January 28-30, 1996, Atlanta, Georgia, United States
	Shay Halperin , Uri Zwick, An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.1-10, June 27-29, 1994, Cape May, New Jersey, United States
	Michele Zito , Ida Pu , Martyn Amos , Alan Gibbons, RCN algorithms for the uniform generation of combinatorial structures, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.429-437, January 28-30, 1996, Atlanta, Georgia, United States
	John Greiner, A comparison of parallel algorithms for connected components, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.16-25, June 27-29, 1994, Cape May, New Jersey, United States
	Ka Wong Chong , Yijie Han , Tak Wah Lam, On the parallel time complexity of undirected connectivity and minimum spanning trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.225-234, January 17-19, 1999, Baltimore, Maryland, United States
	Vladimir Trifonov, An O(log n log log n) space algorithm for undirected st-connectivity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA