Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01592242
Contributor : Nathann Cohen <>
Submitted on : Friday, September 22, 2017 - 9:34:52 PM
Last modification on : Monday, August 3, 2020 - 3:38:29 AM
Document(s) archivé(s) le : Saturday, December 23, 2017 - 2:28:17 PM

File

Outerplanar-JCSS-revised.pdf
Files produced by the author(s)

Identifiers

Citation

Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau Valls, 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⟩

Share

Metrics

Record views

1126

Files downloads

268