Variants of Plane Diameter Completion

Abstract : The {\sc 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 {\sf 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)}}\cdot n$ steps.
Type de document :
Communication dans un congrès
10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Sep 2015, Patras, Grenada. 2015
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225566
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 6 novembre 2015 - 12:11:26
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-01225566, version 1
  • ARXIV : 1509.00757

Collections

Citation

Clément Requilé, Dimitrios M. Thilikos, Petr A. Golovach. Variants of Plane Diameter Completion. 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Sep 2015, Patras, Grenada. 2015. 〈lirmm-01225566〉

Partager

Métriques

Consultations de la notice

34