A polynomial-time algorithm for Outerplanar Diameter Improvement
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-01592242Date
2017Journal name
Journal of Computer and System SciencesVolume
89Publisher
Elsevier
Pages
315-327
Publication identifier
Metadata
Show full item recordAuthor(s)
Cohen, Nathann
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 programmingRelated items
Showing items related by title and author.
-
Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
-
Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié
-
Kim, Eun Jung; Oum, Sang-Il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2015) Communication / Conférence
-
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi (2016) Article accepté pour publication ou publié
-
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi; Sikdar, Somnath (2013-07) Communication / Conférence