ACM DL

Computation Theory (TOCT)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computation Theory (TOCT), Volume 9 Issue 4, December 2017

An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
Diptarka Chakraborty, Raghunath Tewari
Article No.: 19
DOI: 10.1145/3154857

Given a graph G and two vertices s and t in it, 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...