A polynomial-time algorithm for Outerplanar Diameter Improvement

Abstract : The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$, whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2017, 89, pp.315 - 327. 〈10.1016/j.jcss.2017.05.016〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01592242
Contributeur : Nathann Cohen <>
Soumis le : vendredi 22 septembre 2017 - 21:34:52
Dernière modification le : jeudi 26 octobre 2017 - 13:44:08

Fichier

Outerplanar-JCSS-revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau, et al.. A polynomial-time algorithm for Outerplanar Diameter Improvement. Journal of Computer and System Sciences, Elsevier, 2017, 89, pp.315 - 327. 〈10.1016/j.jcss.2017.05.016〉. 〈hal-01592242〉

Partager

Métriques

Consultations de
la notice

129

Téléchargements du document

8