Planar Depth-First Search in O(\log n) Parallel Time
From MaRDI portal
Publication:3474884
DOI10.1137/0219047zbMATH Open0697.68037OpenAlexW2023670982MaRDI QIDQ3474884FDOQ3474884
Authors: Torben Hagerup 
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219047
Recommendations
- Improved parallel depth-first search in undirected planar graphs
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- A linear-processor algorithm for depth-first search in planar graphs
- A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
- A note on parallel depth first search
- Depth-first search in directed planar graphs, revisited
- Depth-First Search in Directed Planar Graphs, Revisited
- Parallel Depth-First Search in General Directed Graphs
- Parallel algorithms for a depth first search and a breadth first search
- Planar Strong Connectivity Helps in Parallel Depth-First Search
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)
Cited In (20)
- A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
- Planar Strong Connectivity Helps in Parallel Depth-First Search
- A parallel algorithm for recognizing unordered depth-first search
- Depth-first search in directed planar graphs, revisited
- A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
- Parallel approximation schemes for problems on planar graphs
- IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH
- An optimal parallel algorithm for planar cycle separators
- A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH
- Depth-First Search Using $$O(n)$$ Bits
- Depth-first search is inherently sequential
- A random NC algorithm for depth first search
- A linear-processor algorithm for depth-first search in planar graphs
- Improved parallel depth-first search in undirected planar graphs
- Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
- Parallel search algorithms for graphs and trees
- An efficient parallel algorithm for shifting the root of a depth first spanning tree
- Parallel depth first search. II: Analysis
- Depth-First Search in Directed Planar Graphs, Revisited
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
This page was built for publication: Planar Depth-First Search in $O(\log n)$ Parallel Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3474884)
