文章基本信息

标题：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