首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem
  • 本地全文:下载
  • 作者:Tetsuo Asano ; David Kirkpatrick ; Kotaro Nakagawa
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to a natural bound O(n^{1/2}). Based on the technique using universal sequences, which has been introduced recently by Asano and Kirkpatrick, we solved this question affirmatively. The main technical contribution is to show a space efficient way to define/construct a cycle-separator that can be used in sublinear computation.

  • 关键词:O(sqrt(n))-space; planar directed graph; polynomial-time; reachability
国家哲学社会科学文献中心版权所有