Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
ACM Transactions on Computation Theory · 2010
DOI: 10.1145/1714450.1714451 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2010. Verfasst von Jan Kynčl und 1 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 9 Literaturangaben.
Abstract (Originalsprache)
Directed reachability (or briefly reachability) is the following decision problem: given a directed graph G and two of its vertices s , t , determine whether there is a directed path from s to t in G . Directed reachability is a standard complete problem for the complexity class NL. Planar reachability is an important restricted version of the reachability problem, where the input graph is planar. Planar reachability is hard for L and is contained in NL but is not known to be NL-complete or contained in L. Allender et al. [2009] showed that reachability for graphs embedded on the torus is logspace-reducible to the planar case. We generalize this result to graphs embedded on a fixed surface of arbitrary genus.
Zitieren
APA
Kynčl, J., & Vyskočil, T. (2010). Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case. ACM Transactions on Computation Theory. https://doi.org/10.1145/1714450.1714451
Vancouver
Kynčl J, Vyskočil T. Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case. ACM Transactions on Computation Theory. 2010. doi:10.1145/1714450.1714451
BibTeX
@article{Kynl2010,
author = {Kynčl, Jan and Vyskočil, Tomáš},
title = {Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case},
journal = {ACM Transactions on Computation Theory},
year = {2010},
doi = {10.1145/1714450.1714451}
}
EUVIMED