A simple parallel tree contraction algorithm
作者： K Abrahamson , N Dadoun , D.G Kirkpatrick , T Przytycka
DOI: 10.1016/0196-6774(89)90017-5
关键词:
摘要: Abstract A simple reduction from the tree contraction problem to list ranking is presented. The takes O(log n) time for a with n nodes, using O( log ) EREW processors. Thus can be done as efficiently ranking. broad class of parallel computations which techniques apply described. This subsumes earlier characterizations. Applications computation certain properties cographs are presented in some detail.
acm.org
elsevier.com
sci-hub.se 参考文章(10)
Uzi Vishkin, Ilan Bar-on, Optimal Parallel Generation of a Computation Tree Form ,(2018)
Gary L. Miller, John H. Reif, Parallel tree contraction and its application 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). pp. 478- 489 ,(1985) , 10.1109/SFCS.1985.43
R Cole, U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms symposium on the theory of computing. pp. 206- 219 ,(1986) , 10.1145/12130.12151
D.G. Corneil, H. Lerchs, L.Stewart Burlingham, Complement reducible graphs Discrete Applied Mathematics. ,vol. 3, pp. 163- 174 ,(1981) , 10.1016/0166-218X(81)90013-5
Uzi Vishkin, Richard Cole, The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time ,(2011)
R.E. Tarjan, U. Vishkin, Finding biconnected componemts and computing tree functions in logarithmic parallel time 25th Annual Symposium onFoundations of Computer Science, 1984.. pp. 12- 20 ,(1984) , 10.1109/SFCS.1984.715896
N. Dadoun, D. G. Kirkpatrick, Parallel processing for efficient subdivision search Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 205- 214 ,(1987) , 10.1145/41958.41980
Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms Journal of the ACM. ,vol. 30, pp. 852- 865 ,(1983) , 10.1145/2157.322410
Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions Journal of the ACM. ,vol. 21, pp. 201- 206 ,(1974) , 10.1145/321812.321815
Richard Cole, Uzi Vishkin, Approximate and exact parallel scheduling with applications to list, tree and graph problems 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). pp. 478- 491 ,(1986) , 10.1109/SFCS.1986.10