EUVIMEDEUVIMED entdecken
Crossref

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

Jan Kynčl, Tomáš Vyskočil

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →