Planar and grid graph reachability problems
From MaRDI portal
Publication:733742
DOI10.1007/s00224-009-9172-zzbMath1183.68409OpenAlexW2072560800MaRDI QIDQ733742
David A. Mix Barrington, Sambuddha Roy, Tanmoy Chakraborty, Samir Datta, Eric W. 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
Related Items (15)
Computational Complexity of Biased Diffusion-Limited Aggregation ⋮ Depth-first search in directed planar graphs, revisited ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ On the power of unambiguity in log-space ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Deterministically isolating a perfect matching in bipartite planar graphs ⋮ String shuffle: circuits and graphs ⋮ Green's theorem and isolation in planar graphs ⋮ Planar and grid graph reachability problems ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Unnamed Item ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ The complexity of solitaire
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Planar and grid graph reachability problems
- Embeddings of graphs with no short noncontractible cycles
- 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
- On truth-table reducibility to SAT
- The relative power of logspace and polynomial time reductions
- Counting quantifiers, successor relations, and logarithmic space
- The complexity of planarity testing
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
- Directed Planar Reachability Is in Unambiguous Log-Space
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- Undirected ST-connectivity in log-space
- Languages that Capture Complexity Classes
- Problems complete for deterministic logarithmic space
- Nondeterministic Space is Closed under Complementation
- Maintenance of a minimum spanning forest in a dynamic plane graph
- An Optimal Parallel Algorithm for Formula Evaluation
- Relativization of questions about log space computability
- Making Nondeterminism Unambiguous
- One-Input-Face MPCVP Is Hard for L, But in LogDCFL
- Evaluating Monotone Circuits on Cylinders, Planes and Tori
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Space efficient algorithms for directed series–parallel graphs
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Planarity, Determinants, Permanents, and (Unique) Matchings
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Planar and grid graph reachability problems
