An optimal parallel connectivity algorithm. (English) Zbl 0546.68044
Summary: A synchronized parallel algorithm of depth \(O(n^ 2/p)\) for p\((\leq n^ 2/\log^ 2n)\) processors is given for the problem of computing connected components of an undirected graph. The speed-up of this algorithm is optimal in the sense that the depth of the algorithm is of the order of the running time of the fastest known sequential algorithm over the number of processors used.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68N25 | Theory of operating systems |
| 05C40 | Connectivity |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Borodin, A.; Hopcroft, J. E., Routing, merging and sorting on parallel models of computation, Proc. 14th ACM Symp. Theory of Computing, 338-344 (1982) |
| [2] | Brent, R. P., The parallel evaluation of general arithmetic expressions, J. ACM, 21, 201-206 (1974) · Zbl 0276.68010 |
| [3] | Cook, S.; Dwork, C., Bounds on the time for the parallel RAM’s to compute simple functions, Proc. 14th ACM Symp. Theory of Computing, 231-233 (1982) |
| [4] | Chin, F. Y.; Lam, J.; Chen, I., Optimal parallel algorithms for the connected component problem, Proc. 1981 Internat. Conf. Parallel Processing, 170-175 (1981) |
| [5] | Eckstein, D. M., Simultaneous memory access, (TR-79-6 (1979), Computer Science Dept., Iowa State University: Computer Science Dept., Iowa State University Ames, IA) |
| [6] | Goldschlager, L. M., A unified approach to models of synchronous parallel computation, Proc. 10 ACM Symp. Theory of Computing, 89-94 (1978) · Zbl 1282.68105 |
| [7] | Hirschberg, D. S.; Chandra, A. K.; Sarwate, D. V., Computing connected components on parallel computers, Comm. ACM, 22, 8, 461-464 (August 1979) · Zbl 0429.68061 |
| [8] | Hirschberg, D. S., Parallel algorithms for the transitive closure and the connected component problem, Proc. 8th ACM Symp. Theory of Computing, Hershey, PA, 55-57 (1976) · Zbl 0369.68022 |
| [9] | Schwartz, J. T., Ultracomputers, ACM Trans. Programming Languages and Systems, 2, 521-848 (1980) · Zbl 0468.68027 |
| [10] | Shiloach, Y.; Vishkin, U., Finding the maximum, merging and sorting in a parallel computation model, J. Algorithms, 2, 88-102 (1981) · Zbl 0456.68062 |
| [11] | Shiloach, Y.; Vishkin, U., An O(log \(n)\) parallel connectivity algorithm, J. Algorithms, 3, 57-67 (1982) · Zbl 0494.68070 |
| [12] | Shiloach, Y.; Vishkin, U., An \(O(n^2\) log \(n)\) parallel max-flow algorithm, J. Algorithms, 3, 128-146 (1982) · Zbl 0483.90044 |
| [13] | Stockmeyer, L. J.; Vishkin, U., Simulation of parallel random access machines by circuits, SIAM J. Comput., 13, 2, 409-422 (1984) · Zbl 0533.68048 |
| [14] | Tarjan, R. E.; Vishkin, U., An efficient parallel biconnectivity algorithm, (TR-69 (1983), Dept. of Computer Science, Courant Institute, NYU), SIAM J. Comput., to appear · Zbl 0575.68066 |
| [15] | Vishkin, U., Implementing simultaneous memory address access in models that forbid it, J. Algorithms, 4, 45-50 (1983) · Zbl 0509.68024 |
| [16] | Vishkin, U., On choice of a model of a parallel computation, (TR-61 (1983), Dept. of Computer Science, Courant Institute, NYU), J. Comput. System Sci., to appear |
| [17] | Wyllie, J. C., The complexity of parallel computation, (Ph.D. Thesis (1979), Dept. of Computer Science, Cornell University: Dept. of Computer Science, Cornell University Ithaca, NY) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
