Depth-first search in directed planar graphs, revisited

DOI10.1007/s00236-022-00425-1OpenAlexW4281622288MaRDI QIDQ2170277

Eric W. 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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum flow in directed planar graphs with vertex capacities
• Green's theorem and isolation in planar graphs
• Planar and grid graph reachability problems
• Depth-first search is inherently sequential
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• Unambiguity of circuits
• Separation of vertices by a circuit
• RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• The complexity of planarity testing
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Logspace optimization problems and their approximability properties
• Depth-First Search Using $$O(n)$$ Bits
• Directed Planar Reachability Is in Unambiguous Log-Space
• Space-efficient Basic Graph Algorithms
• Parallel Depth-First Search in General Directed Graphs
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• Undirected connectivity in log-space
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• Planar Strong Connectivity Helps in Parallel Depth-First Search
• Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
• Making Nondeterminism Unambiguous
• An unambiguous class possessing a complete set
• Computational Complexity
• Parameterized Algorithms
• Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search

This page was built for publication: Depth-first search in directed planar graphs, revisited