Planar Disjoint-Paths Completion

Abstract : We introduce Planar Disjoint Paths Completion, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a, not necessarily connected, plane graph G, k pairs of terminals, and a face F of G, find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an upper bound on the number of necessary additional edges when a solution exists. This bound is a function of k, independent of the size of G. Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time f (k) · n 2 .
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370272
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 22 septembre 2016 - 12:08:55
Dernière modification le : vendredi 5 octobre 2018 - 21:14:01

Fichier

ALGO-D-14-00007 revised submis...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos. Planar Disjoint-Paths Completion. Algorithmica, Springer Verlag, 2015, 76 (2), pp.401-425. 〈http://link.springer.com/article/10.1007/s00453-015-0046-2〉. 〈10.1007/s00453-015-0046-2〉. 〈lirmm-01370272〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

127