License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.30
URN: urn:nbn:de:0030-drops-55697
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5569/
Go to the corresponding LIPIcs Volume Portal

Golovach, Petr A. ; Requilé, Clément ; Thilikos, Dimitrios M.

Variants of Plane Diameter Completion

pdf-format:
6.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{golovach_et_al:LIPIcs:2015:5569,
  author =	{Petr A. Golovach and Cl{\'e}ment Requil{\'e} and Dimitrios M. Thilikos},
  title =	{{Variants of  Plane Diameter Completion}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{30--42},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5569},
  URN =		{urn:nbn:de:0030-drops-55697},
  doi =		{10.4230/LIPIcs.IPEC.2015.30},
  annote =	{Keywords: Planar graphs, graph modification problems, parameterized algorithms, dynamic programming, branchwidth}
}

Keywords: Planar graphs, graph modification problems, parameterized algorithms, dynamic programming, branchwidth
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI