TY - GEN
T1 - Variants of plane diameter completion
AU - Golovach, Petr A.
AU - Requilé, Clément
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Petr A. Golovach, Clément Requilé, and Dimitrios M. Thilikos;.
PY - 2015/11/1
Y1 - 2015/11/1
N2 - 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 κ. In the first variant, called BPDC, κ upper bounds the total number of edges to be added and in the second, called BFPDC, κ 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 κ = 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(n3) + 22O((κd)2 log d) · n steps.
AB - 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 κ. In the first variant, called BPDC, κ upper bounds the total number of edges to be added and in the second, called BFPDC, κ 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 κ = 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(n3) + 22O((κd)2 log d) · n steps.
KW - Branchwidth
KW - Dynamic programming
KW - Graph modification problems
KW - Parameterized algorithms
KW - Planar graphs
UR - http://www.scopus.com/inward/record.url?scp=84958243326&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958243326&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.IPEC.2015.30
DO - 10.4230/LIPIcs.IPEC.2015.30
M3 - Conference contribution
AN - SCOPUS:84958243326
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 30
EP - 42
BT - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015
A2 - Husfeldt, Thore
A2 - Husfeldt, Thore
A2 - Kanj, Iyad
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Y2 - 16 September 2015 through 18 September 2015
ER -