Back to Search
Start Over
A polynomial-time algorithm for Outerplanar Diameter Improvement.
- Source :
-
Journal of Computer & System Sciences . Nov2017, Vol. 89, p315-327. 13p. - Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 89
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 124421778
- Full Text :
- https://doi.org/10.1016/j.jcss.2017.05.016