A unified approach to parallel depth-first traversals of general trees

DOI10.1016/0020-0190(91)90214-3zbMath0736.68032OpenAlexW2049132568MaRDI QIDQ1178197

Selim G. Akl, Sajal K. Das, Calvin C.-Y. Chen

Publication date: 26 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90214-3

zbMATH Keywords

EREW PRAMlinked list rankingtraversal of trees

Mathematics Subject Classification ID

Data structures (68P05) Distributed algorithms (68W15)

Related Items

Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph ⋮ An effective and efficient MapReduce algorithm for computing BFS-based traversals of large-scale RDF graphs ⋮ Breadth-first traversal of trees and integer sorting in parallel ⋮ A simple parallel algorithm for computing the diameters of all vertices in a tree and its application ⋮ An optimal parallel algorithm to construct a tree 3-spanner on interval graphs ⋮ A parallel algorithm to generate all maximal independent sets on permutation graphs ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A parallel search algorithm for directed acyclic graphs
• Parallel algorithms for tree traversals
• A taxonomy of binary tree traversals
• Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
• Fast parallel graph searching with applications
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Parallel breadth-first search algorithms for trees and graphs
• An Efficient Parallel Biconnectivity Algorithm
• Derivation of a parallel algorithm for balancing binary trees
• Deterministic coin tossing with applications to optimal parallel list ranking
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model
• Parallel Computations in Graph Theory
• The Parallel Evaluation of General Arithmetic Expressions