Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-016 | 27th April 2015 14:48

An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

RSS-Feed




Revision #1
Authors: Diptarka Chakraborty, Raghunath Tewari
Accepted on: 27th April 2015 14:48
Downloads: 1410
Keywords: 


Abstract:

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for any $\epsilon > 0$. The previous best known space bound for this problem with polynomial time was approximately $O(\sqrt{n})$ space \cite{INPVW13}.

Deciding graph reachability in {\SC} is an important open question in complexity theory and in this paper we make progress towards resolving this question.


Paper:

TR15-016 | 16th January 2015 07:35

An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs





TR15-016
Authors: Diptarka Chakraborty, Raghunath Tewari
Publication: 31st January 2015 15:59
Downloads: 2212
Keywords: 


Abstract:

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for any $\epsilon > 0$. The previous best known space bound for this problem with polynomial time was approximately $O(\sqrt{n})$ space \cite{INPVW13}.

Deciding graph reachability in {\SC} is an important open question in complexity theory and in this paper we make progress towards resolving this question.



ISSN 1433-8092 | Imprint