The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
From MaRDI portal
Publication:1104105
DOI10.1007/BF01762121zbMath0646.68081OpenAlexW2034282023MaRDI QIDQ1104105
Uzi Vishkin, Richard John Cole
Publication date: 1988
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01762121
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (23)
Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ Parallel computation on interval graphs: algorithms and experiments ⋮ Improved parallel depth-first search in undirected planar graphs ⋮ An optimal parallel algorithm for planar cycle separators ⋮ AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS ⋮ A centroid labelling technique and its application to path selection in trees ⋮ A simple randomized parallel algorithm for list-ranking ⋮ Parallel recognition of complement reducible graphs and cotree construction ⋮ A unified approach to parallel depth-first traversals of general trees ⋮ Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees ⋮ Collection depots facility location problems in trees ⋮ An optimal algorithm for the maximum-density path in a tree ⋮ Efficient parallel algorithms for r-dominating set and p-center problems on trees ⋮ Efficient parallel algorithms for graph problems ⋮ Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ Computing Prüfer codes efficiently in parallel ⋮ Faster optimal parallel prefix sums and list ranking ⋮ Balancing straight-line programs for strings and trees ⋮ Fast algorithms for approximate Fréchet matching queries in geometric trees ⋮ Deterministic parallel list ranking ⋮ On optimal parallel computations for sequences of brackets ⋮ Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- On efficient parallel strong orientation
- Faster optimal parallel prefix sums and list ranking
- Optimal parallel generation of a computation tree form
- An Efficient Parallel Biconnectivity Algorithm
- Deterministic coin tossing with applications to optimal parallel list ranking
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- On the Parallel Evaluation of Certain Arithmetic Expressions
This page was built for publication: The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
