A polynomial-time algorithm for Outerplanar Diameter Improvement

作者：

Highlights：

• The goal of Outerplanar Diameter Improvement is to add edges to a graph G to obtain an outerplanar graph of diameter at most D.

• We provide a dynamic programming algorithm that solves the problem in polynomial time.

• This problem has structural analogues to the open problem Planar Diameter Improvement, where the resulting graph should be planar.

摘要

•The goal of Outerplanar Diameter Improvement is to add edges to a graph G to obtain an outerplanar graph of diameter at most D.•We provide a dynamic programming algorithm that solves the problem in polynomial time.•This problem has structural analogues to the open problem Planar Diameter Improvement, where the resulting graph should be planar.

论文关键词：Diameter improvement,Outerplanar graphs,Completion problems,Polynomial-time algorithms,Dynamic programming

论文评审过程：Received 20 January 2015, Revised 13 January 2017, Accepted 29 May 2017, Available online 13 June 2017, Version of Record 7 August 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.05.016