On the parallel time complexity of undirected connectivity and minimum spanning trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the parallel time complexity of undirected connectivity and minimum spanning trees

Full text

Pdf (1.18 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 225 - 234

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

Ka Wong Chong	Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany
Yijie Han	Electronic Data Systems, Inc., 750 Tower Drive, Mail Stop 7121, CPS, Troy, MI
Tak Wah Lam	Department of Computer Science, The University of Hong Kong, Hong Kong

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

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

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	Bernard Chazelle, A Faster Deterministic Algorithm for Minimum Spanning Trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.22, October 19-22, 1997
	3	K.W. Chong, Finding Minimum Spanning Trees on the EREW PRAM, Proc. international Computer Symposium, 1996, pp. 7-14.
	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	Richard Cole , Philip N. Klein , Robert E. Tarjan, Finding minimum spanning forests in logarithmic time and linear work using random sampling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.243-250, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237563]
	6	R. Cole and U. Vishkin, Approximate and Exact Parallel Scheduling with Applications to List, Tree, and Graph Problems, FOCS'86, pp. 478-491.
	7	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]
	8	H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
	9	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	10	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]
	11	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]
	12	David Ron Karger, Random sampling in graph optimization problems, Stanford University, Stanford, CA, 1995
	13	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]
	14	David R. Karger , Noam Nisan , Michal Parnas, Fast connected components algorithms for the EREW PRAM, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.373-381, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141920]
	15	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
	16	Chung Keung Poon , Vijaya Ramachandran, A Randomized Linear Work EREW PRAM Algorithm to Find a Minimum Spanning Forest, Proceedings of the 8th International Symposium on Algorithms and Computation, p.212-222, December 17-19, 1997
	17	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	18	R.E. Tarjan and U. Vishkin, An Efficient Parallel Biconnectivity Algorithm, SIAM J. Comput., 14(1985), pp. 862-874.

CITED BY 2

	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
	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