Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case

DOI10.1145/1714450.1714451zbMath1322.68107OpenAlexW1988076846MaRDI QIDQ2947545

Tomáš Vyskočil, Jan Kynčl

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1714450.1714451

zbMATH Keywords

graphs on surfacesdirected graph reachabilitylog-space reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (4)

On the power of unambiguity in log-space ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Derandomizing Isolation in Space-Bounded Settings

This page was built for publication: Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case