Depth-first search in directed planar graphs, revisited
From MaRDI portal
Publication:2170277
DOI10.1007/S00236-022-00425-1OpenAlexW4281622288MaRDI QIDQ2170277FDOQ2170277
Authors: Eric Allender, Archit Chauhan, Samir Datta
Publication date: 30 August 2022
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00236-022-00425-1
Cites Work
- Computational Complexity
- Undirected connectivity in log-space
- Parameterized Algorithms
- Depth-first search is inherently sequential
- Parallel Depth-First Search in General Directed Graphs
- Planar Depth-First Search in $O(\log n)$ Parallel Time
- Planar Strong Connectivity Helps in Parallel Depth-First Search
- Title not available (Why is that?)
- Making Nondeterminism Unambiguous
- Logspace optimization problems and their approximability properties
- Planar and grid graph reachability problems
- Title not available (Why is that?)
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Directed Planar Reachability Is in Unambiguous Log-Space
- Green's theorem and isolation in planar graphs
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- Separation of vertices by a circuit
- Maximum flow in directed planar graphs with vertex capacities
- Depth-First Search Using $$O(n)$$ Bits
- Space-efficient Basic Graph Algorithms
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
- The complexity of planarity testing
- RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
- An unambiguous class possessing a complete set
- Unambiguity of circuits
- Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
- Title not available (Why is that?)
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
- Title not available (Why is that?)
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
Cited In (5)
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)