Journal
THEORETICAL COMPUTER SCIENCE
Volume 982, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2023.114251
Keywords
Graph reachability; Simultaneous time-space upper bound; Tree decomposition
Categories
Ask authors/readers for more resources
To solve the reachability problem is to determine if there is a path between two vertices in a graph. This paper studies space-efficient algorithms that run in polynomial time to decide reachability. An algorithm is presented that solves reachability in directed graphs using O(n log n) space.
To solve reachability is to determine whether there is a path from one vertex to the other in a graph. Standard graph traversal algorithms such as DFS and BFS take linear time to solve reachability; however, their space complexity is also linear. On the other hand, Savitch's algorithm takes quasipolynomial time, although the space-bound is ������(log2 ������). In this paper, we study space-efficient algorithms for deciding reachability that runs in polynomial time. We show a polynomial-time algorithm that solves reachability in directed graphs using ������(������ log ������) space. Our algorithm requires access to a tree decomposition of width ������for the underlying undirected graph of the input. This requirement can be waived for graphs for which recursive balanced vertex separators can be computed space-efficiently.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available