Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
DOI10.1016/0012-365X(93)90375-4zbMATH Open0787.68081MaRDI QIDQ685690FDOQ685690
Publication date: 24 October 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
Recommendations
- On the recognition of search trees generated by BFS and DFS
- A parallel algorithm for recognizing unordered depth-first search
- Parallel recognition algorithms for chordal-planar graphs and planar \(k\)-trees
- Series - parallel graphs and depth-first search trees
- The recognition problem of graph search trees
- Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata
- A unified approach to parallel depth-first traversals of general trees
- Automated verification of parallel nested DFS
- Recognizing breadth-first search trees in linear time
parallel algorithmdepth-first searchgraph algorithmsacyclic graphCREW PRAMDFS treerefined verification
Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distributed algorithms (68W15)
Cites Work
- Depth-First Search and Linear Graph Algorithms
- Efficient Planarity Testing
- Depth-first search is inherently sequential
- On finding optimal and near-optimal lineal spanning trees
- A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
- Title not available (Why is that?)
- Parallel Prefix Computation
- An Efficient Parallel Biconnectivity Algorithm
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Dividing a Graph into Triconnected Components
- Title not available (Why is that?)
- A new distributed depth-first-search algorithm
- On efficient parallel strong orientation
- A random NC algorithm for depth first search
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- A parallel algorithm for recognizing unordered depth-first search
- Series - parallel graphs and depth-first search trees
- An efficient parallel algorithm for shifting the root of a depth first spanning tree
- Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
Cited In (7)
- Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
- A parallel algorithm for recognizing unordered depth-first search
- On the recognition of search trees generated by BFS and DFS
- Depth-first search is inherently sequential
- Series - parallel graphs and depth-first search trees
- A new distributed depth-first-search algorithm
- The Recognition Problem of Graph Search Trees
Uses Software
This page was built for publication: Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685690)
