An O ( n ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

DOI10.1145/3154857zbMath1427.68232arXiv1501.05828OpenAlexW1486144962MaRDI QIDQ4973896

Diptarka Chakraborty, Raghunath Tewari

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.05828

zbMATH Keywords

time-space tradeoffdirected reachability problemlayered grid graphlayered planar graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Space-efficient algorithms for reachability in directed geometric graphs ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators

This page was built for publication: An O ( n ^ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs