Directed Planar Reachability Is in Unambiguous Log-Space
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.
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}
}
EUVIMED