Title: $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
Abstract: The directed graph reachability problem takes as input an n-vertex directed graph G = (V,E), and two distinguished vertices v 0, and vertex v *. The problem is to determine whether there exists a path from v 0 to v * in G. The main result of this paper is to show that the directed graph reachability problem restricted to planar graphs can be solved in polynomial time using only $\widetilde{O}(\sqrt{n})$ space.
Publication Year: 2014
Publication Date: 2014-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 16
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot