Efficient parallel algorithms for some graph problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient parallel algorithms for some graph problems

Full text

Pdf (710 KB)

Source

Communications of the ACM archive
Volume 25 , Issue 9 (September 1982) table of contents

Pages: 659 - 665

Year of Publication: 1982

ISSN:0001-0782

Authors

Francis Y. Chin	Univ. of Alberta, Edmonton, Alberta, Canada
John Lam	Univ. of Alberta, Edmonton, Alberta, Canada
I-Ngo Chen	Univ. of Alberta, Edmonton, Alberta, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 116, Citation Count: 29

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

ABSTRACT

We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O(log2 n) time bound can be achieved using only K = n⌈n/log2 n⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.

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	Baudet, G. and D. Stevenson. Optimal sorting algorithms for parallel computers, IEEE Trans. on Computers C-27, (Jan. 1978) 84- 87.
	2	Berge, C. and Chouila-Houri, A. Programming, Games and Transportation Networks. Wiley, New York, 1965, p. 179.
	3	Chandra, A.K. Maximal parallelism in matrix multiplication. IBM Research Report, RC 6193, 1976.
	4	Crane, B.A. Path finding with associative memory. IEEE Trans. on Computers C-17, 7 (July 1968) 691-693.
	5	Csanky, L. On the parallel complexity of some computational problems. Ph.D. Dissertation, Comp. Sci. Division, U. of California, Berkeley, 1974.
	6	Eckstein, D.M. and D.A. Alton. Parallel graph processing using depth-first search. Conf. on Theoretical Comp. Sci., U. of Waterloo, 1977, 21-29.
	7	Flynn, M. Some computer organizations and their effectiveness. IEEE Trans. on Computers C-21, 9 (Sept. 1972) 9948-960.
	8	Leslie Michael Goldschlager, Synchronous parallel computation., 1978
	9	Heller D. A Survey of parallel algorithms in numerical linear algebra. SIAM Review, 20 4 (Oct. 1978) 740-777.
	10	D. S. Hirschberg, Parallel algorithms for the transitive closure and the connected component problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.55-57, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803631]
	11	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]
	12	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]
	13	Hyafil, L. and H.T. Kung. Parallel algorithms for solving triangular linear systems with small parallelism. Dept. of Comp. Sci., Carnegie-Mellon U., Pittsburgh, Pa., 1974.
	14	David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977 [doi>10.1145/356683.356686]
	15	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]
	16	Munro, I. and M. Paterson. Optimal algorithms for parallel polynomial evaluation. JCSS, 7, 2 (April 1973) 189-198.
	17	Preparata, F.P. New parallel-sorting schemes. IEEE Trans. on Computers C-27, 7 (July 1978) 669-673.
	18	Reghbati, E. and D.G. Corneil. Parallel computations in graph theory. SIAM J. Computing, 7, 2 (May 1978) 230-237.
	19	Savage, C.D. Parallel algorithms for graph theoretical problems. Ph.D, Dissertation, R-784, Dept. of Math., U. of Illinois, Urbana, 1977.
	20	Joseph F. Traub, Complexity of Sequential and Parallel Numerical Algorithms, Academic Press, Inc., Orlando, FL, 1973
	21	Harold S. Stone, An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations, Journal of the ACM (JACM), v.20 n.1, p.27-38, Jan. 1973 [doi>10.1145/321738.321741]
	22	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 29

	Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, 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
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	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
	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
	Ilan Bar-on , Uzi Vishkin, Optimal parallel generation of a computation tree form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.348-357, April 1985
	Weifa Liang , Richard P. Brent , Hong Shen, Fully Dynamic Maintenance of k-Connectivity in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.12 n.8, p.846-864, August 2001
	Kameshwar Munagala , Abhiram Ranade, I/O-complexity of graph algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.687-694, January 17-19, 1999, Baltimore, Maryland, 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
	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
	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
	S. Upendra Rao , G. P. Shattacharjee , A. K. Majumdar, Parallel implementation of an efficient microcode compaction algorithm, ACM SIGMICRO Newsletter, v.17 n.3, p.13-19, Dec. 1986
	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
	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
	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
	Chang-Wu Yu , Gen-Huey Chen, An Efficient Parallel Recognition Algorithm For Bipartite-Permutation Graphs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.3-10, January 1996
	Ten H. Lai , Ming-Jye Sheng, Constructing Euclidean Minimum Spanning Trees and All Nearest Neighbors on Reconfigurable Meshes, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.806-817, August 1996
	Hussein M. Alnuweiri, Parallel Constant-Time Connectivity Algorithms on a Reconfigurable Network of Processors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.1, p.105-110, January 1995
	K. W. Ryu , J. JáJ', Efficient Algorithms for List Ranking and for Solving Graph Problems on the Hypercube, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.83-90, January 1990
	Lars Arge , Gerth Stølting Brodal , Laura Toma, On external-memory MST, SSSP and multi-way planar graph separation, Journal of Algorithms, v.53 n.2, p.186-206, November 2004
	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
	Lars Arge , Michael A. Bender , Erik D. Demaine , Bryan Holland-Minkley , J. Ian Munro, Cache-oblivious priority queue and graph algorithm applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Hirotoshi Honma , Shigeru Masuyama, An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.9, p.2296-2300, September 2008