An efficient and fast parallel-connected component algorithm

ABSTRACT

A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of e edges and n nodes, the time complexity of the algorithm is &Ogr;(e/p + (n log n)/p + log2n) with p processors. The algorithm can be further refined to yield time complexity &Ogr;(H(e, n, p)/p + (n log n)/(p log(n/p)) + log2n), where H(e, n, p) is very close to &Ogr;(e). These results show that linear speedup can be obtained for up to p ≤ e/log2n processors when e ≥ n log n. Linear speedup can still be achieved with up to p ≤ n&egr; processors, 0 ≤ &egr; < 1, for graphs satisfying e ≥ n log(*)n. Our results can be further improved if a more efficient integer sorting algorithm is available.

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: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• 3: AWERBUCH, B., AND SHILOACH, Y. New connectivity and MSF algorithms for ultracomputer and PRAM. In Proceedings of the 1983 International Conference on Parallel Processing (Aug.). IEEE, New York, 1983, pp. 175-179.
• 4: A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
• 5: 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]
• 6: Y. Han, Designing fast and efficient parallel algorithms, Duke University, Durham, NC, 1987
• 7: 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]
• 8: HIRSCHBERG, D.S. Parallel graph algorithms without memory conflicts. In Proceedings of the 20th Allerton Conference. Univ. of Illinois, Urbana-Champaign, Ill., 1982, pp. 257-263.
• 9: 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]
• 10: KRUSKAL, C. P., RUDOLPH, L., AND SNIR, M. The power of parallel prefix. IEEE Tran. Comput. C-34, l0 (Oct. 1985), 965-968.
• 11: KRUSKAL, C. P., RUDOLPH, L. AND SNIR, M. Efficient parallel algorithms for graph problems. In Proceedings of the 1986 International Conference on Parallel Processing (Aug.). IEEE, New York, 1986, pp. 278-284.
• 12: KU(~ERA, L. Parallel computation and conflicts in memory access. Inf. Process. Lett. 14, 2 (20 Apr. 1982), 93-96.
• 13: KWAN, S. C. AND RUZZO, W. L. Adaptive parallel algorithms for finding minimum spanning trees. In Proceedings of the 1984 International Conference on Parallel Processing (Aug.). IEEE, New York, 1984, pp. 439-443.
• 14: LEV, G. F., PIPPENGER, N., AND VALIANT, L. G. A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput. C-30 (Feb. 1981), 93-100.
• 15: NATH, D., AND MAHESHWARI, S. N. Parallel algorithms for the connected components and minimal spanning tree problems. Inf. Proc. Lett. 14, 1 (27 Mar. 1982), 7-11.
• 16: Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984 [doi>10.1145/2514.2515]
• 17: REGHBATI(ARJOMANIDI), E., AND CORNEIL, D.G. Parallel computations in graph theory. SIAM J. Comput. 2, 2 (May 1978), 230-237.
• 18: John H. Reif, Symmetric complementation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.201-214, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802193]
• 19: SAVAGE, C., AND JA'JA, J. Fast, efficient parallel algorithms for some graph problems. SlAM J. Comput. 10, 4 (Nov. 1981), 682-690.
• 20: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 21: SHILOACH, Y., AND VISHKIN, U. An O(log n) parallel connectivity algorithm. J. Algor. 3, l (Mar. 1982), 57-67.
• 22: SNIR, M. On parallel searching. SIAM J. Comput. 14, 3 (Aug. 1985), 688-708.
• 23: WAGNER, R., AND HAN, Y. Parallel algorithms for bucket sorting and the data dependent prefix problem. In Proceedings of the 1986 International Conference on Parallel Processing (Aug.). IEEE, New York, 1986, pp. 924-930.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Theory