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

文章基本信息

  • 标题:Computing Bounded Path Decompositions in Logspace
  • 本地全文:下载
  • 作者:Shiva Kintali ; Sinziana Munteanu
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We present a logspace algorithm to compute path decompositions of bounded pathwidth graphs, thus settling its complexity. Prior to our work, the best known upper bound to compute such decompositions was linear time. We also show that deciding if the pathwidth of a graph is at most a given constant is L-complete. Besides being of fundamental interest, our results represent an important step to gain a better understanding of the complexity of Graph Isomorphism of bounded pathwidth graphs.

  • 关键词:Logspace; path decompositions; pathwidth; tree decompositions; Treewidth
国家哲学社会科学文献中心版权所有