A polynomial-time algorithm for Outerplanar Diameter Improvement

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

doi:10.1016/j.jcss.2017.05.016

A polynomial-time algorithm for Outerplanar Diameter Improvement

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

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	315-327
Number of pages	13
Journal	Journal of Computer and System Sciences
Volume	89
DOIs	https://doi.org/10.1016/j.jcss.2017.05.016
State	Published - Nov 2017

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.jcss.2017.05.016

Cite this

@article{56c09f7c319149d5bf700df734f0722f,

title = "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.",

keywords = "Completion problems, Diameter improvement, Dynamic programming, Outerplanar graphs, Polynomial-time algorithms",

author = "Nathann Cohen and Daniel Gon{\c c}alves and Kim, {Eun Jung} and Christophe Paul and Ignasi Sau and Thilikos, {Dimitrios M.} and Mathias Weller",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2017",

month = nov,

doi = "10.1016/j.jcss.2017.05.016",

language = "English (US)",

volume = "89",

pages = "315--327",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - A polynomial-time algorithm for Outerplanar Diameter Improvement

AU - Cohen, Nathann

AU - Gonçalves, Daniel

AU - Kim, Eun Jung

AU - Paul, Christophe

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

AU - Weller, Mathias

PY - 2017/11

Y1 - 2017/11

N2 - 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.

AB - 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.

KW - Completion problems

KW - Diameter improvement

KW - Dynamic programming

KW - Outerplanar graphs

KW - Polynomial-time algorithms

UR - http://www.scopus.com/inward/record.url?scp=85020864937&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85020864937&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2017.05.016

DO - 10.1016/j.jcss.2017.05.016

M3 - Article

AN - SCOPUS:85020864937

SN - 0022-0000

VL - 89

SP - 315

EP - 327

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

A polynomial-time algorithm for Outerplanar Diameter Improvement

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this