文章基本信息

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