Planar and grid graph reachability problems
From MaRDI portal
Publication:733742
DOI10.1007/S00224-009-9172-ZzbMATH Open1183.68409OpenAlexW2072560800MaRDI QIDQ733742FDOQ733742
Authors: David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy, Eric Allender 
Publication date: 19 October 2009
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-009-9172-z
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
- On truth-table reducibility to SAT
- Graphs on surfaces
- Title not available (Why is that?)
- Relativization of questions about log space computability
- Embeddings of graphs with no short noncontractible cycles
- Problems complete for deterministic logarithmic space
- Nondeterministic Space is Closed under Complementation
- Languages that Capture Complexity Classes
- Maintenance of a minimum spanning forest in a dynamic plane graph
- The method of forced enumeration for nondeterministic automata
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Embedding planar graphs in four pages
- Faster shortest-path algorithms for planar graphs
- An Optimal Parallel Algorithm for Formula Evaluation
- Making Nondeterminism Unambiguous
- One-Input-Face MPCVP Is Hard for L, But in LogDCFL
- Undirected ST-connectivity in log-space
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Counting quantifiers, successor relations, and logarithmic space
- Planarity, Determinants, Permanents, and (Unique) Matchings
- Planar and grid graph reachability problems
- Evaluating Monotone Circuits on Cylinders, Planes and Tori
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Directed planar reachability is in unambiguous log-space
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- Space efficient algorithms for directed series–parallel graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of planarity testing
- The relative power of logspace and polynomial time reductions
- Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
Cited In (21)
- Planar and grid graph reachability problems
- Reachability Problems: An Update
- Depth-first search in directed planar graphs, revisited
- String shuffle: circuits and graphs
- Deterministically isolating a perfect matching in bipartite planar graphs
- Space complexity of perfect matching in bounded genus bipartite graphs
- On the complexity of two-dimensional signed majority cellular automata
- Green's theorem and isolation in planar graphs
- Title not available (Why is that?)
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Computational Complexity of Biased Diffusion-Limited Aggregation
- Interdiction problems on planar graphs
- The complexity of solitaire
- Space-efficient algorithms for reachability in directed geometric graphs
- Reachability problems in edge-colored digraphs
- On the power of unambiguity in log-space
- Compressed Decision Problems in Hyperbolic Groups.
- \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- On reachability in graphs with obstacles
- Log-space algorithms for paths and matchings in \(k\)-trees
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)
