Depth-first search in directed planar graphs, revisited

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)

Title not available (Why is that?)
Title not available (Why is that?)
Relational depth-first-search with applications
Planar Depth-First Search in $O(\log n)$ Parallel Time
Depth-First Search in Directed Planar Graphs, Revisited

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)