Finding minimum spanning forests in logarithmic time and linear work using random sampling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding minimum spanning forests in logarithmic time and linear work using random sampling

Full text

Pdf (864 KB)

Source

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

Padua, Italy

Pages: 243 - 250

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Richard Cole	New York University
Philip N. Klein	Brown University
Robert E. Tarjan	Department of Computer Science, Princeton University, Princeton, NJ and NEC Research Institute, Princeton, NJ

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): 5, Downloads (12 Months): 35, Citation Count: 9

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/237502.237563 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	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]
	2	O. Borfivka. "O jist6m probl6mu minim#ln#m, Prdca Moravsk# P#rodov#deck# Spoledao,ti 3, 1926, pp. 37-58. (In Czech.)
	3	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]
	4	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
	5	R. Cole, P. N. Klein, and R. E. Tarjan, "A linear-work parallel algorithm for finding minimum spanning trees," 6th Annual ACM Symposium on Parallel Algorithms and Architectures (1994), pp. 11-15.
	6	R. Cole and U. Vishkin, "Approximate and exact parallel scheduling with applications to list, tree, and graph problems," Proc. 27th Annual IEEE Syrup. on Foundations of Computsr Science, 1986, pp. 478-491.
	7	Brandon Dixon , Monika Rauch , Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing, v.21 n.6, p.1184-1192, Dec. 1992 [doi>10.1137/0221070]
	8	B. Dixon and R. E. Tarjan, "Optimal parallel verification of minimum spanning trees in logarithmic time," .4 lg o r2#h m# ca, to appear.
	9	M. Fredman and D. E. Willard, "Trans-dichotomous algorithms fc)r minimum spanning trees and shortest paths," Proc, 31#t Ann#c#l tEEN S#mp. on Fo#ndat#on# of Co,nputer 5c#e#ce., IEEE Computer Society Press, Los Alamitos, ('A, 1986, pp. 478-491.
	10	Hillel Gazit, An optimal randomized parallel algorithm for finding connected components in a graph, SIAM Journal on Computing, v.20 n.6, p.1046-1067, Dec. 1991 [doi>10.1137/0220066]
	11	Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
	12	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 [doi>10.1145/181014.181017]
	13	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
	14	Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
	15	"O jist6m probl6mu minim#ilnfm," Prdca Morttvski Pr{rodovedecki Spolecno#t# 6 (1930), pp. 57-63. (In Czech.)
	16	Donald B. Johnson , Panagiotis Metaxas, A parallel algorithm for computing minimum spanning trees, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.363-372, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141917]
	17	D. R. Karger, "Approximating, verifying, and constructing minimum spanning forests," manuscript, 1992.
	18	D. R. Karger '*Random sampling in matroids, with applications to graph connectivity and minimum spanning trees," Proc. ,34st Ann#al IEEE Syrup. on Fowndatzoas of Computer Science, IE1LE Computer Society Press, Los Alamitos, CA, 1993, pp. 84-93.
	19	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
	20	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	21	Valerie King, A Simpler Minimum Spanning Tree Verification Algorithm, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.440-448, August 16-18, 1995
	22	V. King, personal communication, 1994.
	23	Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm for finding minimum spanning trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.9-15, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195084]
	24	N. Megiddo, "Parallel algorithms for finding the maximum and the median almost surely in constant time," Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, October 1982.
	25	P. 1%aghavan, "'Lecture Notes on Randomized Algorithms," Research 1%eport 1%C 15340 (#68237), Computer Science/Mathematics IBM Research Division, T.J. Watson Research Center, #%rktown Heights, NY. 1990, p. 54.
	26	C. Savage and .J. Ja'Ja, "Fast efficient parallel algorithms for some graph problems, SIAM J. Co mput 10 1981, pp. 682.
	27	Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
	28	Y. Shiloach, U. Vishkin. "Finding the maximum, merging and sortmg in a parallel computation model," Journal of Algorithms, 1(1981 ). 88-102.
	29	Y. Shiloach and U. Vishkin, "An O(log n) parallel connectivity algorithm." J. Algorithms 2, 1982, pp. 57-67.
	30	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

CITED BY 9

	Micah Adler , Wolfgang Dittrich , Ben Juurlink , Mirosław Kutyłowski , Ingo Rieping, Communication-optimal parallel minimum spanning tree algorithms (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.27-36, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Ka Wong Chong , Yijie Han , Yoshihide Igarashi , Tak Wah Lam, Improving the efficiency of parallel minimum spanning tree algorithms, Discrete Applied Mathematics, v.126 n.1, p.33-54, March 2003
	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
	Seth Pettie , Vijaya Ramachandran, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.713-722, January 06-08, 2002, San Francisco, California
	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
	Zvi Lotker , Elan Pavlov , Boaz Patt-Shamir , David Peleg, MST construction in O(log log n) communication rounds, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
	David A. Bader , Guojing Cong, Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs, Journal of Parallel and Distributed Computing, v.66 n.11, p.1366-1378, November 2006
	Seth Pettie , Vijaya Ramachandran, Randomized minimum spanning tree algorithms using exponentially fewer random bits, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-27, March 2008