A polynomial-time algorithm for outerplanar diameter improvement

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

doi:10.1007/978-3-319-20297-6_9

A polynomial-time algorithm for outerplanar diameter improvement

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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)
Title of host publication	Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings
Editors	Lev D. Beklemishev, Daniil V. Musatov, Daniil V. Musatov
Publisher	Springer Verlag
Pages	123-142
Number of pages	20
ISBN (Print)	9783319202969
DOIs	https://doi.org/10.1007/978-3-319-20297-6_9
State	Published - 2015
Event	10th International Computer Science Symposium in Russia, CSR 2015 - Listvyanka, Russian Federation Duration: Jul 13 2015 → Jul 17 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9139
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Computer Science Symposium in Russia, CSR 2015
Country/Territory	Russian Federation
City	Listvyanka
Period	7/13/15 → 7/17/15

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-20297-6_9

Cite this

Cohen, N., Gonçalves, D., Kim, E., Paul, C., Sau, I., Thilikos, D. M., & Weller, M. (2015). A polynomial-time algorithm for outerplanar diameter improvement. In L. D. Beklemishev, D. V. Musatov, & D. V. Musatov (Eds.), Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings (pp. 123-142). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9139). Springer Verlag. https://doi.org/10.1007/978-3-319-20297-6_9

A polynomial-time algorithm for outerplanar diameter improvement. / Cohen, Nathann; Gonçalves, Daniel; Kim, Eunjung et al.
Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. ed. / Lev D. Beklemishev; Daniil V. Musatov; Daniil V. Musatov. Springer Verlag, 2015. p. 123-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9139).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cohen, N, Gonçalves, D, Kim, E, Paul, C, Sau, I, Thilikos, DM & Weller, M 2015, A polynomial-time algorithm for outerplanar diameter improvement. in LD Beklemishev, DV Musatov & DV Musatov (eds), Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9139, Springer Verlag, pp. 123-142, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russian Federation, 7/13/15. https://doi.org/10.1007/978-3-319-20297-6_9

Cohen N, Gonçalves D, Kim E, Paul C, Sau I, Thilikos DM et al. A polynomial-time algorithm for outerplanar diameter improvement. In Beklemishev LD, Musatov DV, Musatov DV, editors, Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. Springer Verlag. 2015. p. 123-142. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-20297-6_9

Cohen, Nathann ; Gonçalves, Daniel ; Kim, Eunjung et al. / A polynomial-time algorithm for outerplanar diameter improvement. Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. editor / Lev D. Beklemishev ; Daniil V. Musatov ; Daniil V. Musatov. Springer Verlag, 2015. pp. 123-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7a7b6f0b8b3b4f52911991ec85844f5c,

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 Eunjung Kim and Christophe Paul and Ignasi Sau and Thilikos, {Dimitrios M.} and Mathias Weller",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 10th International Computer Science Symposium in Russia, CSR 2015 ; Conference date: 13-07-2015 Through 17-07-2015",

year = "2015",

doi = "10.1007/978-3-319-20297-6_9",

language = "English (US)",

isbn = "9783319202969",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "123--142",

editor = "Beklemishev, {Lev D.} and Musatov, {Daniil V.} and Musatov, {Daniil V.}",

booktitle = "Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings",

}

TY - GEN

T1 - A polynomial-time algorithm for outerplanar diameter improvement

AU - Cohen, Nathann

AU - Gonçalves, Daniel

AU - Kim, Eunjung

AU - Paul, Christophe

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

AU - Weller, Mathias

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

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=84950118730&partnerID=8YFLogxK

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

U2 - 10.1007/978-3-319-20297-6_9

DO - 10.1007/978-3-319-20297-6_9

M3 - Conference contribution

AN - SCOPUS:84950118730

SN - 9783319202969

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 123

EP - 142

BT - Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings

A2 - Beklemishev, Lev D.

A2 - Musatov, Daniil V.

PB - Springer Verlag

T2 - 10th International Computer Science Symposium in Russia, CSR 2015

Y2 - 13 July 2015 through 17 July 2015

ER -

A polynomial-time algorithm for outerplanar diameter improvement

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this