Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs
From MaRDI portal
Publication:2821694
DOI10.1007/978-3-319-05446-9_3zbMath1345.68149OpenAlexW192770227MaRDI QIDQ2821694
Publication date: 22 September 2016
Published in: Perspectives in Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-05446-9_3
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Green's theorem and isolation in planar graphs
- The method of forced enumeration for nondeterministic automata
- A very hard log-space counting class
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Relationships between nondeterministic and deterministic tape complexities
- Directed Planar Reachability Is in Unambiguous Log-Space
- Nondeterministic Space is Closed under Complementation
- Space Lower Bounds for Maze Threadability on Restricted Machines
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Making Nondeterminism Unambiguous