Parallel Depth-First Search in General Directed Graphs
DOI10.1137/0219025zbMATH Open0692.68053OpenAlexW2020283440MaRDI QIDQ3034839FDOQ3034839
Alok Aggarwal, Ming-Yang Kao, Richard J. Anderson
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219025
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Graph theory (05C99) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (27)
- Title not available (Why is that?)
- A unified approach to parallel depth-first traversals of general trees
- Depth-first search in directed planar graphs, revisited
- A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
- Frameworks for designing in-place graph algorithms
- Bipartite Perfect Matching is in Quasi-NC
- An optimal parallel algorithm for planar cycle separators
- A random NC algorithm for depth first search
- Fault tolerant depth first search in undirected graphs: simple yet efficient
- Title not available (Why is that?)
- Improved parallel depth-first search in undirected planar graphs
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Title not available (Why is that?)
- Parallel search algorithms for graphs and trees
- A randomized NC algorithm for the maximal tree cover problem
- Parallel complexity of computing a maximal set of disjoint paths
- A model classifying algorithms as inherently sequential with applications to graph searching
- Parallel algorithms for a depth first search and a breadth first search
- Not all planar digraphs have small cycle separators
- Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier
- Size-estimation framework with applications to transitive closure and reachability
- Relational depth-first-search with applications
- Planar Depth-First Search in $O(\log n)$ Parallel Time
- Scalable Parallel DFPN Search
- Depth-First Search in Directed Planar Graphs, Revisited
- A Framework for In-place Graph Algorithms
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
This page was built for publication: Parallel Depth-First Search in General Directed Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034839)
