$\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability

DOI10.1007/978-3-662-44465-8_5zbMath1426.68196OpenAlexW206903853MaRDI QIDQ2922595

Osamu Watanabe, Kotaro Nakagawa, David G. Kirkpatrick, Tetsuo Asano

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-44465-8_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (10)

Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Depth-First Search Using $$O(n)$$ Bits ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Unnamed Item ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ Space efficient linear time algorithms for BFS, DFS and applications

This page was built for publication: $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability