EUVIMEDEUVIMED entdecken
Crossref

Directed Planar Reachability Is in Unambiguous Log-Space

Chris Bourke, Raghunath Tewari, N. V. Vinodchandran

ACM Transactions on Computation Theory · 2009

DOI: 10.1145/1490270.1490274 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2009. Verfasst von Chris Bourke und 2 weiteren Autor:innen. Die Arbeit wurde bisher 34-mal zitiert (Crossref) und nennt 26 Literaturangaben. Gefördert von: Division of Computing and Communication Foundations.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We make progress in understanding the complexity of the graph reachability problem in the context of unambiguous logarithmic space computation; a restricted form of nondeterminism. As our main result, we show a new upper bound on the directed planar reachability problem by showing that it can be decided in the class unambiguous logarithmic space (UL). We explore the possibility of showing the same upper bound for the general graph reachability problem. We give a simple reduction showing that the reachability problem for directed graphs with thickness two is complete for the class nondeterministic logarithmic space (NL). Hence an extension of our results to directed graphs with thickness two will unconditionally collapse NL to UL.

Förderung

  • Division of Computing and Communication Foundations

Zitieren

APA

Bourke, C., Tewari, R., & Vinodchandran, N. V. (2009). Directed Planar Reachability Is in Unambiguous Log-Space. ACM Transactions on Computation Theory. https://doi.org/10.1145/1490270.1490274

Vancouver

Bourke C, Tewari R, Vinodchandran NV. Directed Planar Reachability Is in Unambiguous Log-Space. ACM Transactions on Computation Theory. 2009. doi:10.1145/1490270.1490274

BibTeX
@article{Bourke2009,
  author = {Bourke, Chris and Tewari, Raghunath and Vinodchandran, N. V.},
  title = {Directed Planar Reachability Is in Unambiguous Log-Space},
  journal = {ACM Transactions on Computation Theory},
  year = {2009},
  doi = {10.1145/1490270.1490274}
}
Kostenlos starten →