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 algorithmgraph algorithmsdepth-first searchCREW PRAMacyclic graphDFS treerefined verification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Distributed algorithms (68W15)

Related Items (3)

Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ The Recognition Problem of Graph Search Trees ⋮ On the recognition of search trees generated by BFS and DFS

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

This page was built for publication: Recognition of DFS trees: Sequential and parallel algorithms with refined verifications