article

Free access

Computing connected components on parallel computers

Authors:

D. S. Hirschberg,

D. V. SarwateAuthors Info & Claims

Communications of the ACM, Volume 22, Issue 8

Pages 461 - 464

https://doi.org/10.1145/359138.359141

Published: 01 August 1979 Publication History

Abstract

We present a parallel algorithm which uses n² processors to find the connected components of an undirected graph with n vertices in time O(log²n). An O(log²n) time bound also can be achieved using only n⌈n/⌈log₂n⌉⌉ 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

[1]

Aho, AN., Hopcroft, J.E., and Ullman, J.D. The Design and Analysis o f Computer Algorithms, Addison-Wesley, Reading, Mass., 1974.

Digital Library

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

Brent, R.P. The parallel evaluation of general arithmetic expressions. J. ACM 21, (April 1974), 201-206.

Digital Library

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

Hirschberg, D.S. Fast parallel sorting algorithms. Comm. ACM 21, 8 (Aug. 1978), 657-661.

Digital Library

[8]

Hyafil, L., and Kung, H.T. The complexity of parallel evaluation of linear recurrences. J. ACM 24, (July 1977), 513-521.

Digital Library

[9]

Levitt, K.N., and Kautz, W.H. Cellular arrays for the solution of graph problems. Comm. ACM 15, (Sept. 1972), 789-801.

Digital Library

[10]

Munro, I., }nd Paterson, M. Optimal algorithms for parallel polynomial evaluation. J. Comp. Syst. Sci. 7 (1973), 183-198.

Digital Library

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

Digital Library

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

Thompson, C.D., and Kung, H.T. Sorting on a mesh-connected parallel computer. Comm. A CM 20, 4 (April 1977), 263-271.

Digital Library

Cited By

Peechapat WPuttanapong N(2024)Collaboration and Competition: A Social Network Analysis of Thailand’s Music IndustryEconomies10.3390/economies1202004512:2(45)Online publication date: 12-Feb-2024
https://doi.org/10.3390/economies12020045
Sheng ZZhang WTao YCui B(2024)OUTRE: An OUT-of-Core De-REdundancy GNN Training Framework for Massive Graphs within A Single MachineProceedings of the VLDB Endowment10.14778/3681954.368197617:11(2960-2973)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3681976
Jiang ZZhang SHou XYuan MYou H(2024)IVE: Accelerating Enumeration-Based Subgraph Matching via Exploring Isolated Vertices2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00321(4208-4221)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00321
Show More Cited By

Computing connected components on parallel computers
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

The Parallel Recognition of Classes of Graphs

Parallel cellular algorithms for recognizing adjacency and incidence matrices of several classes of graphs are given. These classes include cubic graphs, complete graphs, connected graphs, and trees.
Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
Special Issue on SODA'11

This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O(mn) time and answers queries in constant time. Previously, such ...
Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory

This paper presents BSR-parallel algorithms for some problems in fundamental graph theory : transitive closure, connected components, spanning tree, bridges and articulation points of a graph and bipartite graph recognition. There already exist constant ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 22, Issue 8

Aug. 1979

40 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359138

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Copyright © 1979 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1979

Published in CACM Volume 22, Issue 8

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

219
Total Citations
View Citations
1,513
Total Downloads

Downloads (Last 12 months)180
Downloads (Last 6 weeks)24

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Peechapat WPuttanapong N(2024)Collaboration and Competition: A Social Network Analysis of Thailand’s Music IndustryEconomies10.3390/economies1202004512:2(45)Online publication date: 12-Feb-2024
https://doi.org/10.3390/economies12020045
Sheng ZZhang WTao YCui B(2024)OUTRE: An OUT-of-Core De-REdundancy GNN Training Framework for Massive Graphs within A Single MachineProceedings of the VLDB Endowment10.14778/3681954.368197617:11(2960-2973)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3681976
Jiang ZZhang SHou XYuan MYou H(2024)IVE: Accelerating Enumeration-Based Subgraph Matching via Exploring Isolated Vertices2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00321(4208-4221)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00321
Sharma SLi Q(2024)Super-Node Approximation With Convex Hulls Relaxation for Distribution System Restoration Using ERRsIEEE Access10.1109/ACCESS.2024.341554812(85061-85071)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3415548
Bhat SAbulaish M(2024)A MapReduce-Based Approach for Fast Connected Components Detection from Large-Scale NetworksBig Data10.1089/big.2022.0264Online publication date: 29-Jan-2024
https://doi.org/10.1089/big.2022.0264
Liang FZhao HWang ZFang WShi CFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Retrieving GNN Architecture for Collaborative FilteringProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615035(1379-1388)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3615035
Reif JSpirakis P(2023)Expected parallel time and sequential space complexity of graph and digraph problemsAlgorithmica10.1007/BF017587797:1-6(597-630)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01758779
Liu STarjan R(2022)Simple Concurrent Connected Components AlgorithmsACM Transactions on Parallel Computing10.1145/35435469:2(1-26)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1145/3543546
Bayat NMa RMisra VRubenstein D(2022)Big Winners and Small Losers of Zero-ratingACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/35397317:1(1-24)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1145/3539731
Dang DLin BSahoo D(2022)LiteCON: An All-photonic Neuromorphic Accelerator for Energy-efficient Deep LearningACM Transactions on Architecture and Code Optimization10.1145/353122619:3(1-22)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1145/3531226
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents