首页    期刊浏览 2024年07月19日 星期五
登录注册

文章基本信息

  • 标题:An O ( n ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
  • 本地全文:下载
  • 作者:Diptarka Chakraborty ; Raghunath Tewari
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Given a graph G and two vertices s and t in it, {\em graph reachability} is the problem of checking whether there exists a path from s to t in G . We show that reachability in directed layered planar graphs can be decided in polynomial time and O ( n ) space, for any 0"> 0 . The previous best known space bound for this problem with polynomial time was approximately O ( n ) space \cite{INPVW13}.

    Deciding graph reachability in {\SC} is an important open question in complexity theory and in this paper we make progress towards resolving this question.

  • 关键词:layered grid graph ; layered planar graph ; rechability
国家哲学社会科学文献中心版权所有