4.3 Article

Space efficient algorithm for solving reachability using tree decomposition and separators

期刊

THEORETICAL COMPUTER SCIENCE
卷 982, 期 -, 页码 -

出版社

ELSEVIER
DOI: 10.1016/j.tcs.2023.114251

关键词

Graph reachability; Simultaneous time-space upper bound; Tree decomposition

向作者/读者索取更多资源

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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据