Yujie Han
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 Ο(e/p + (n log n)/p + log2n) with p processors. The algorithm can be further refined to yield time complexity Ο(H(e, n, p)/p + (n log n)/(p log(n/p)) + log2n), where H(e, n, p) is very close to Ο(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ε processors, 0 ≤ ε < 1, for graphs satisfying e ≥ n log(*)n. Our results can be further improved if a more efficient integer sorting algorithm is available.
- 1 AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1973, p. 133. Google Scholar
- 2 AJ'rgI, M., KOML0S, J., AND SZEMEREDI, E. An O(n log n) sorting network. In Proceedings of the 15th ACM Symposium on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New York, 1983, pp. 1-9. Google Scholar
- 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.Google Scholar
- 4 BORODIN, R. A., AND HOPCROFT, J. E. Routing, merging, and sorting on parallel models of computation. In Proceedings of the 14th ACM Symposium on Theory of Computing (San Francisco, Calif., May 5-7). ACM, New York, 1982, pp. 338-344. Google Scholar
- 5 CHIN, F. Y., LAM, J., AND CHEN, I.-N. Efficient parallel algorithms for some graph problems. Commun. ACM 25, 9 (Sept. 1982), 659-665. Google Scholar
- 6 HAN, Y. Designing fast and efficient parallel algorithms. Ph.D. dissertation, Dept. Computer Sci., Duke Univ., Durham, N.C., 1987. Google Scholar
- 7 HIRSCHBERG, D. S. Parallel algorithms for the transitive closure and the connected component problem. In Proceedings of the 8th ACM Symposium on Theory of Computing (Hershey, PP., May 3-5). ACM, New York, 1976, pp. 55-57. Google Scholar
- 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.Google Scholar
- 9 HmSCHBFRG, D. S., CHANDRA, A. K., AND SARWATE, O.V. Computing connected components on parallel computers. Commun. ACM. 22, 8 (Aug. 1979), pp. 461-464. Google Scholar
- 10 KRUSKAL, C. P., RUDOLPH, L., AND SNIR, M. The power of parallel prefix. IEEE Tran. Comput. C-34, l0 (Oct. 1985), 965-968.Google Scholar
- 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.Google Scholar
- 12 KU(~ERA, L. Parallel computation and conflicts in memory access. Inf. Process. Lett. 14, 2 (20 Apr. 1982), 93-96.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 16 QUINN, M., AND DEO, N. Parallel graph algorithms. ACM Comput. Surv. 16, 3 (Sept. 1984), 319-348. Google Scholar
- 17 REGHBATI(ARJOMANIDI), E., AND CORNEIL, D.G. Parallel computations in graph theory. SIAM J. Comput. 2, 2 (May 1978), 230-237.Google Scholar
- 18 REIF, J.H. Symmetric complementation. In Proceedings of the 14th ACM Symposium on Theory of Computing (San Francisco, Calif., May 5-7). ACM, New York, 1982, pp. 201-214. Google Scholar
- 19 SAVAGE, C., AND JA'JA, J. Fast, efficient parallel algorithms for some graph problems. SlAM J. Comput. 10, 4 (Nov. 1981), 682-690.Google Scholar
- 20 SCHWARTZ, J.Z. Ultracomputers. ACM Trans. Prog. Lang. Syst. (Oct. 1~80), pp. 484-521. Google Scholar
- 21 SHILOACH, Y., AND VISHKIN, U. An O(log n) parallel connectivity algorithm. J. Algor. 3, l (Mar. 1982), 57-67.Google Scholar
- 22 SNIR, M. On parallel searching. SIAM J. Comput. 14, 3 (Aug. 1985), 688-708.Google Scholar
- 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.Google Scholar
Index Terms
- An efficient and fast parallel-connected component algorithm
Recommendations
Fast Connected Components Algorithms for the EREW PRAM
We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm ...
Fast and Efficient Parallel Coarsest Refinement
The process of merging two arbitrary partitions of a given finite set 𝒰 of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions 𝒳, 𝒴 of the set 𝒰 such that 𝒳 = {𝒳1, 𝒳2, ..., 𝒳x} and 𝒴...
Comments