A polynomial-time algorithm for Outerplanar Diameter Improvement

Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M.

Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017), A polynomial-time algorithm for Outerplanar Diameter Improvement, Journal of Computer and System Sciences, 89, p. 315-327. 10.1016/j.jcss.2017.05.016

Type

Article accepté pour publication ou publié

External document link

https://hal.inria.fr/hal-01592242

Date

2017

Journal name

Journal of Computer and System Sciences

Volume

Publisher

Elsevier

Pages

315-327

Gonçalves, Daniel

Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paul, Christophe

Sau Valls, Ignasi

Thilikos, Dimitrios M.

Abstract (EN)

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.

Subjects / Keywords

Diameter improvement; Outerplanar graphs; Completion problems; Polynomial-time algorithms; Dynamic programming