Depth-first search in directed planar graphs, revisited
From MaRDI portal
Publication:2170277
Recommendations
- Depth-First Search in Directed Planar Graphs, Revisited
- Planar Depth-First Search in $O(\log n)$ Parallel Time
- Improved parallel depth-first search in undirected planar graphs
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- Planar Strong Connectivity Helps in Parallel Depth-First Search
Cites work
- scientific article; zbMATH DE number 4209587 (Why is no real title available?)
- scientific article; zbMATH DE number 45125 (Why is no real title available?)
- scientific article; zbMATH DE number 1346519 (Why is no real title available?)
- scientific article; zbMATH DE number 1161568 (Why is no real title available?)
- An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
- An unambiguous class possessing a complete set
- Computational Complexity
- Depth-First Search Using $$O(n)$$ Bits
- Depth-first search is inherently sequential
- Directed planar reachability is in unambiguous log-space
- Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
- Green's theorem and isolation in planar graphs
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
- Logspace optimization problems and their approximability properties
- Making Nondeterminism Unambiguous
- Maximum flow in directed planar graphs with vertex capacities
- Parallel Depth-First Search in General Directed Graphs
- Parameterized algorithms
- Planar Depth-First Search in $O(\log n)$ Parallel Time
- Planar Strong Connectivity Helps in Parallel Depth-First Search
- Planar and grid graph reachability problems
- Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
- RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
- Separation of vertices by a circuit
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- Space-efficient basic graph algorithms
- The complexity of planarity testing
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Unambiguity of circuits
- Undirected connectivity in log-space
Cited in
(5)- scientific article; zbMATH DE number 1069483 (Why is no real title available?)
- scientific article; zbMATH DE number 3990867 (Why is no real title available?)
- Relational depth-first-search with applications
- Depth-First Search in Directed Planar Graphs, Revisited
- Planar Depth-First Search in $O(\log n)$ Parallel Time
This page was built for publication: Depth-first search in directed planar graphs, revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170277)
