Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
From MaRDI portal
Publication:685690
DOI10.1016/0012-365X(93)90375-4zbMath0787.68081MaRDI QIDQ685690
Publication date: 24 October 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
parallel algorithm; graph algorithms; depth-first search; CREW PRAM; acyclic graph; DFS tree; refined verification
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
Uses Software
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
