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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)315-327
Number of pages13
JournalJournal of Computer and System Sciences
Volume89
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'A polynomial-time algorithm for Outerplanar Diameter Improvement'. Together they form a unique fingerprint.

Cite this