Computing connected components on parallel computers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing connected components on parallel computers

Full text

Pdf (406 KB)

Source

Communications of the ACM archive
Volume 22 , Issue 8 (August 1979) table of contents

Pages: 461 - 464

Year of Publication: 1979

ISSN:0001-0782

Authors

D. S. Hirschberg	Rice Univ., Houston, TX
A. K. Chandra	IBM Thomas J. Watson Research Center, Yorktown Heights, NY
D. V. Sarwate	Univ. of Illinois, Urbana

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 80, Citation Count: 31

Additional Information:

abstract 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/359138.359141 What is a DOI?

ABSTRACT

We present a parallel algorithm which uses n2 processors to find the connected components of an undirected graph with n vertices in time O(log2n). An O(log2n) time bound also can be achieved using only n⌈n/⌈log2n⌉⌉ processors. The algorithm can be used to find the transitive closure of a symmetric Boolean matrix. We assume that the processors have access to a common memory. Simultaneous access to the same location is permitted for fetch instructions but not for store instructions.

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Batcher, K.E. Sorting networks and their applications. Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N.J., pp. 307- 314.
	3	Baudet, G., and Stevenson, D. Optimal sorting algorithms for parallel computers. 1EEE Trans. Comptrs. C-27 (Jan. 1978), 84-87.
	4	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	5	Chandra, A.K. Maximal parallelism in matrix multiplication. IBM Tech. Rep. RC6193, Sept. 1976.
	6	Csanky, L. Fast parallel matrix inversion algorithms, SlAM J. Comping. 5 (Dec. 1976), 618-623.
	7	D. S. Hirschberg, Fast parallel sorting algorithms, Communications of the ACM, v.21 n.8, p.657-661, Aug. 1978 [doi>10.1145/359576.359582]
	8	L. Hyafil , H. T. Kung, The Complexity of Parallel Evaluation of Linear Recurrences, Journal of the ACM (JACM), v.24 n.3, p.513-521, July 1977 [doi>10.1145/322017.322030]
	9	K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972 [doi>10.1145/361573.361576]
	10	Munro, I., }nd Paterson, M. Optimal algorithms for parallel polynomial evaluation. J. Comp. Syst. Sci. 7 (1973), 183-198.
	11	Pan, V.Y. Strassen's algorithm is not optimal. Proc. 19th Annu. Symp. on Foundations of Comptr. Sci., 1978, pp. 166-176.
	12	Preparata, F.P. New parallel-sorting schemes. IEEE Trans. Comptrs. C-27 (July 1978), 669-673.
	13	Preparata, F.P., and Sarwate, D.V. An improved parallel processor bound in fast matrix inversion. Inf. Proc. Letters 7 (April 1978), 148-150.
	14	Reghbati, E., and Corneil, D.C. Parallel computations in graph theory. SlAM J. Comping. 7 (May 1978), 230-237.
	15	Savage, C.D. Parallel algorithms for graph theoretic problems. Ph.D. Th., U. of Illinois, Urbana, I11., Aug. 1977.
	16	C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977 [doi>10.1145/359461.359481]

CITED BY 31

	M Li , Y Yesha, New lower bounds for parallel computation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.177-187, May 28-30, 1986, Berkeley, California, United States
	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
	J. Naor , M. Naor , A. Schaffer, Fast parallel algorithms for chordal graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.355-364, January 1987, New York, New York, 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
	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
	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
	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
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, 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
	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
	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
	John H. Reif, Symmetric Complementation, Journal of the ACM (JACM), v.31 n.2, p.401-421, April 1984
	Zbigniew M. Wójcik , Barbara E. Wójcik, Principles of the parallel shape coding with the termination condition, Proceedings of the 19th annual conference on Computer Science, p.391-401, April 1991, San Antonio, Texas, United States
	Ming Li , Yaacov Yesha, New lower bounds for parallel computation, Journal of the ACM (JACM), v.36 n.3, p.671-680, July 1989
	Kenji Suzuki , Isao Horiba , Noboru Sugie, Linear-time connected-component labeling based on sequential local operations, Computer Vision and Image Understanding, v.89 n.1, p.1-23, January 2003
	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
	B. F. Wang , G. H. Chen, Constant Time Algorithms for the Transitive Closure and Some Related Graph Problems on Processor Arrays with Reconfigurable Bus Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.500-507, October 1990
	Joseph Já Já, The VLSI Complexity of Selected Graph Problems, Journal of the ACM (JACM), v.31 n.2, p.377-391, April 1984
	Yujie Han , Robert A. Wagner, An efficient and fast parallel-connected component algorithm, Journal of the ACM (JACM), v.37 n.3, p.626-642, July 1990
	D. A. Carlson, Modified-Mesh Connected Parallel Computers, IEEE Transactions on Computers, v.37 n.10, p.1315-1321, October 1988
	Russ Miller , V. K. Prasanna-Kumar , Dionisios I. Reisis , Quentin F. Stout, Parallel Computations on Reconfigurable Meshes, IEEE Transactions on Computers, v.42 n.6, p.678-692, June 1993
	G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989
	R. Cypher , J. L. C. Sanz , L. Snyder, An EREW PRAM Algorithm for Image Component Labeling, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.3, p.258-262, March 1989
	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
	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
	Nageswara S. V. Rao, On Parallel Algorithms for Single-Fault Diagnosis in Fault Propagation Graph Systems, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1217-1223, December 1996
	David A. Bader , Guojing Cong, A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs), Journal of Parallel and Distributed Computing, v.65 n.9, p.994-1006, September 2005
	C. A. Philips, Parallel graph contraction, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.148-157, June 18-21, 1989, Santa Fe, New Mexico, United States
	Stavros D. Nikolopoulos , Leonidas Palios, On the parallel computation of the biconnected and strongly connected co-components of graphs, Discrete Applied Mathematics, v.155 n.14, p.1858-1877, September, 2007
	Lifeng He , Yuyan Chao , Kenji Suzuki , Kesheng Wu, Fast connected-component labeling, Pattern Recognition, v.42 n.9, p.1977-1987, September, 2009

INDEX TERMS

Keywords:
algorithms, connected component, graph theory, parallel processing, transitive closure

Collaborative Colleagues:

D. S. Hirschberg: colleagues

A. K. Chandra: colleagues

D. V. Sarwate: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player