首页    期刊浏览 2024年11月10日 星期日
登录注册

文章基本信息

  • 标题:Variants of Plane Diameter Completion
  • 本地全文:下载
  • 作者:Petr A. Golovach ; Cl{\'e}ment Requil{\'e ; Dimitrios M. Thilikos
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2015
  • 卷号:43
  • 页码:30-42
  • DOI:10.4230/LIPIcs.IPEC.2015.30
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:The Plane Diameter Completion problem asks, given a plane graph G and a positive integer d, if it is a spanning subgraph of a plane graph H that has diameter at most d. We examine two variants of this problem where the input comes with another parameter k. In the first variant, called BPDC, k upper bounds the total number of edges to be added and in the second, called BFPDC, k upper bounds the number of additional edges per face. We prove that both problems are NP-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when k=1 on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in O(n^{3})+2^{2^{O((kd)^2\log d)}} * n steps.
  • 关键词:Planar graphs; graph modification problems; parameterized algorithms; dynamic programming; branchwidth
国家哲学社会科学文献中心版权所有