Dynamic parallel tree contraction (extended abstract)

ABSTRACT

Parallel tree contraction has been found to be a useful and quite powerful tool for the design of a wide class of efficient graph algorithms. We propose a corresponding technique for the parallel solution of incremental problems. As our computational model, we assume a variant of the CRCW PRAM where we can dynamically activate processors by a forking operation. We consider a dynamic binary tree T of ≤ n nodes and unbounded depth. We describe a procedure, which we call the dynamic parallel tree contraction algorithm, which incrementally processes various parallel modification requests and queries: (1)parallel requests to add or delete leaves of T, or modify labels of internal nodes or leaves of T, and also (2) parallel tree contraction queries which require recomputing values at specified nodes. Each modification or query is with respect to a set of nodes U in T. Our dynamic parallel tree contraction algorithm is a randomized algorithm that takes O(log(|U|log n)) expected parallel time using O(|U|log n/log(|U|log n) processors. We give a large number of applications (with the same bounds), including: (a) maintaining the usual tree properties (such as number of ancestors, preorder, etc.), (b) Eulerian tour, (c) expression evaluation, (d) least common ancestor, and (e) canonical forms of trees. Previously, there where no known parallel algorithms for incrementally maintaining and solving such problems in parallel time less than &THgr;(log n). In deriving our incremental algorithms, we solve a key subproblem, namely a processor activation problem, within the same asymptotic bounds, which may be useful in the design of other parallel incremental algorithms. This algorithm uses an interesting persistent parallel data structures involving a non-trivial construction. In a subsequent paper, we apply our dynamic parallel tree contraction technique to various incremental graph problems: maintaining various properties, (such as coloring, minimum covering set, maximum matching, etc.). of parallel series graphs, outerplanar graphs, Helin networks, bandwidth-limited networks, and various other graphs with constant separator size.

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: D. Armon and J.H. Reif, "Strictly Polylog Time, Linear Space Algorithms for Nearest Neighbor Search and Dynamic Separators in d Dimensions", manuscript, Oct 1992
• 3: Robert F. Cohen , Roberto Tamassia, Dynamic expression trees and their applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.52-61, January 28-30, 1991, San Francisco, California, United States
• 4: Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
• 5: Greg N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, Proceedings of the 32nd annual symposium on Foundations of computer science, p.632-641, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185429]
• 6: Greg N. Frederickson, A data structure for dynamically maintaining rooted trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.175-184, January 25-27, 1993, Austin, Texas, United States
• 7: H. Gazit, G. L. Miller, and S. H. Teng. "Optimal Tree Contraction in the EREW Model", in Concurrent Computations: Algorithms, Architecture, and Technology, Plenum, New York, pp. 139-156, 1988.
• 8: Xin He , Yaacov Yesha, Binary tree algebraic computation and parallel algorithms for simple graphs, Journal of Algorithms, v.9 n.1, p.92-113, March 1988 [doi>10.1016/0196-6774(88)90007-7]
• 9: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 10: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 11: S. R. Kosaraju , A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• 12: G. L. Miller and J. H. Reif. "Parallel Tree Contraction Part 1: Fundamentals", in Randomness and Computation, Vol. 5, S. Micali, ed., JAI Press, Greenwich, CT, pp. 47-72, 1989.
• 13: Gary L. Miller , John H. Reif, Parallel tree contraction part 2: further applications, SIAM Journal on Computing, v.20 n.6, p.1128-1147, Dec. 1991 [doi>10.1137/0220070]
• 14: J. Ian Munro , Thomas Papadakis , Robert Sedgewick, Deterministic skip lists, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.367-375, September 1992, Orlando, Florida, United States
• 15: J.H. Reif, P. Spirakis, M. Yung, "Re-Randomization and Average Case Analysis of Fully Dynamic Graph Algorithms ", manuscript, Oct, 1992.
• 16: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Theory, Verification