文章基本信息
- 标题：A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs
- 本地全文：下载
- 作者：Ryo Ashida ; Tatsuya Imai ; Kotaro Nakagawa 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2019
- 卷号：2019
- 页码：1-42
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses O ( n 1 2+ ) space. A critical ingredient of their algorithm is a polynomial-time, \tldO ( n ) -space algorithm to compute a separator of a planar graph. The conference version provided a sketch of the algorithm and many nontrivial details were left unexplained. In this work, we provide a detailed construction of their algorithm.
- 关键词：planar graph ; Planar Separator ; sublinear algorithms ; Time-Space Efficient Algorithms
