Planar and grid graph reachability problems
From MaRDI portal
Recommendations
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Reachability Problems: An Update
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
- \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
- Directed planar reachability is in unambiguous log-space
Cites work
- scientific article; zbMATH DE number 4006288 (Why is no real title available?)
- scientific article; zbMATH DE number 1263189 (Why is no real title available?)
- scientific article; zbMATH DE number 6146491 (Why is no real title available?)
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- An Optimal Parallel Algorithm for Formula Evaluation
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Counting quantifiers, successor relations, and logarithmic space
- Directed planar reachability is in unambiguous log-space
- Embedding planar graphs in four pages
- Embeddings of graphs with no short noncontractible cycles
- Evaluating Monotone Circuits on Cylinders, Planes and Tori
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Faster shortest-path algorithms for planar graphs
- Graphs on surfaces
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Languages that Capture Complexity Classes
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Making Nondeterminism Unambiguous
- Nondeterministic Space is Closed under Complementation
- On truth-table reducibility to SAT
- One-Input-Face MPCVP Is Hard for L, But in LogDCFL
- Planar and grid graph reachability problems
- Planarity, Determinants, Permanents, and (Unique) Matchings
- Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
- Problems complete for deterministic logarithmic space
- Relativization of questions about log space computability
- Space efficient algorithms for directed series–parallel graphs
- The complexity of planarity testing
- The method of forced enumeration for nondeterministic automata
- The relative power of logspace and polynomial time reductions
- Undirected ST-connectivity in log-space
Cited in
(21)- Green's theorem and isolation in planar graphs
- Planar and grid graph reachability problems
- \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
- On reachability in graphs with obstacles
- Deterministically isolating a perfect matching in bipartite planar graphs
- Depth-first search in directed planar graphs, revisited
- The complexity of solitaire
- Space complexity of perfect matching in bounded genus bipartite graphs
- On the power of unambiguity in log-space
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Reachability Problems: An Update
- scientific article; zbMATH DE number 7650316 (Why is no real title available?)
- Space-efficient algorithms for reachability in directed geometric graphs
- Interdiction problems on planar graphs
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Log-space algorithms for paths and matchings in \(k\)-trees
- Compressed Decision Problems in Hyperbolic Groups.
- On the complexity of two-dimensional signed majority cellular automata
- Computational Complexity of Biased Diffusion-Limited Aggregation
- String shuffle: circuits and graphs
- Reachability problems in edge-colored digraphs
This page was built for publication: Planar and grid graph reachability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733742)
