zbMATH — the first resource for mathematics

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree. (English) Zbl 0860.68053
Summary: The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graph \(G=(V, E_G)\) and an MST \(T\) for \(G\), find a new MST for \(G\) to which a new vertex \(z\) has been added along with weighted edges that connect \(z\) with the vertices of \(G\). We present a set of rules that produce simple optimal parallel algorithms that run in \(O(\text{lg }n)\) time using \(n/\text{lg }n\) EREW PRAM processors, where \(n=|V|\). These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that used \(n\) processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST when \(k\) new vertices are introduced simultaneously. This problem is solved in \(O(\text{lg }k\cdot\text{lg }n)\) parallel time using \((k\cdot n)/(\text{lg }k\cdot\text{lg }n)\) EREW PRAM processors. This is optimal for graphs having \(\Omega(kn)\) edges.

68W10 Parallel algorithms in computer science
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] R. Brent. The parallel evaluation of general arithmetic expressions.Journal of the ACM, 21(2):201–206, 1974. · Zbl 0276.68010 · doi:10.1145/321812.321815
[2] R. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines.Handbook for Theoretical Computer Science, 1:869–941, 1990. · Zbl 0900.68267
[3] P. M. Spira and A. Pan. On finding and updating spanning trees and shortest paths.SIAM Journal on Computing, 4(3):375–380, September 1975. · Zbl 0325.05119 · doi:10.1137/0204032
[4] F. Chin and D. Houck. Algorithms for updating minimal spanning trees.Journal of Computer and System Sciences, 16(12):333–344, 1978. · Zbl 0381.05025 · doi:10.1016/0022-0000(78)90022-3
[5] S. Pawagi and I. V. Ramakrishnan. AnO(logn) algorithm for parallel update of minimum spanning trees.Information Processing Letters, 22(5):223–229, April 1986. · Zbl 0592.68061 · doi:10.1016/0020-0190(86)90098-0
[6] P. Varman and K. Doshi. A parallel vertex insertion algorithm for minimum spanning trees.Proceedings of 13th ICALP, pages 424–433. Lecture Notes in Computer Science, volume 226. Springer-Verlag, Berlin, 1986. · Zbl 0594.68044
[7] H. Jung and K. Mehlhorn. Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees.Information Processing Letters, 27(5):227–236, April 1988. · Zbl 0637.68046 · doi:10.1016/0020-0190(88)90084-1
[8] D. B. Johnson and P. Metaxas. A parallel algorithm for computing minimum spanning trees.Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’92)], pages 363–372, June 1992.
[9] K. W. Chong and T. W. Lam. Finding connected components inO(logn log logn) time on the EREW PRAM.Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, pages 11–20, January 1993. · Zbl 0801.68123
[10] D. B. Johnson and P. Metaxas. Optimal algorithms for the vertex updating problem of a minimum spanning tree.Proceedings of the 6th International Parallel Proccessing Symposium (IPPS ’92), pages 306–314, March 1992.
[11] F. Y. Chin, J. Lam, and I-N. Chen. Efficient parallel algorithms for some graph problems.Communications of ACM, 25(9):659–665, September 1982. · Zbl 0485.68056 · doi:10.1145/358628.358650
[12] R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time.Algorithmica, 3:329–346, 1988. · Zbl 0646.68081 · doi:10.1007/BF01762121
[13] G. L. Miller and J. H. Reif. Parallel tree contraction. Part 1: Fundamentals.Advances in Computing Research, 5:47–72, 1989.
[14] K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka. A simple parallel tree contraction algorithm.Journal of Algorithms, 10:287–302, 1989. · Zbl 0681.68085 · doi:10.1016/0196-6774(89)90017-5
[15] S. Rao Kosaraju and A. L. Deicher. Optimal parallel evaluation of tree-structured computations by raking.Proceedings of the Aegean Workshop on Computing, pages 101–110, 1988.
[16] A. Gibbons and W. Rytter. An optimal parallel algorithm for dynamic expression evaluation and its applications.Proceedings of the Symposium on Foundations of Software Technology and Theoretical Computer Science, volume 6, pages 453–469. Springer-Verlag, New York, 1986. · Zbl 0623.68037
[17] H. Gazit, G. L. Miller, and S. H. Teng. Optimal tree contraction in the EREW model. InConcurrent Computations: Algorithms, Architecture, and Technology, S. K. Tewksbury, B. W. Dickinson, and S. C. Schwartz (editors), Plenum, New York, pages 139–170, 1988.
[18] R. E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm.SIAM Journal of Computing, 14(4):862–874, 1985. · Zbl 0575.68066 · doi:10.1137/0214061
[19] S. Cook, C. Dwork, and R. Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes.SIAM Journal of Computing, 15(1):87–97, February 1986. · Zbl 0591.68049 · doi:10.1137/0215006
[20] R. Cole and U. Vishkin. Approximate parallel scheduling. Part 1: The basic technique with applications to optimal parallel list ranking in logarithmic time.SIAM Journal of Computing, 17(1): 128–142, February 1988. · Zbl 0637.68038 · doi:10.1137/0217009
[21] R. J. Anderson and G. L. Miller. Deterministic parallel list ranking.Algorithmica, 6:859–868, 1991. · Zbl 0732.68045 · doi:10.1007/BF01759076
[22] S. Pawagi. A parallel algorithm for multiple updates of minimum spanning trees.Proceedings of the International Conference on Parallel Processing, volume III, pages 9–15, 1989.
[23] S. Pawagi and O. Kaser. Optimal parallel algorithms for multiple updates of minimum spanning trees. Technical Report, Department of Computer Science, SUNY at Stony Brook, 1991. Unpublished Manuscript. · Zbl 0768.68027
[24] A. Schäffer and P. Varman. Parallel batch update of minimum spanning trees. Technical report, Department of Electrical and Computer Engineering, Rice University, May 1991. Unpublished Manuscript.
[25] R. E. Tarjan.Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983. · Zbl 0584.68077
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.