Recognition of DFS trees: Sequential and parallel algorithms with refined verifications

DOI10.1016/0012-365X(93)90375-4zbMath0787.68081MaRDI QIDQ685690

Zvi Ostfeld, Ephraim Korach

Publication date: 24 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

parallel algorithm; graph algorithms; depth-first search; CREW PRAM; acyclic graph; DFS tree; refined verification

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

68W15: Distributed algorithms

Related Items

The Recognition Problem of Graph Search Trees, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Depth-first search is inherently sequential
• A new distributed depth-first-search algorithm
• On efficient parallel strong orientation
• A random NC algorithm for depth first search
• On finding optimal and near-optimal lineal spanning trees
• A parallel algorithm for recognizing unordered depth-first search
• Series - parallel graphs and depth-first search trees
• An Efficient Parallel Biconnectivity Algorithm
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Parallel Prefix Computation
• Efficient Planarity Testing
• Dividing a Graph into Triconnected Components
• Depth-First Search and Linear Graph Algorithms