A polynomial-time algorithm for outerplanar diameter improvement

DOI10.1016/j.jcss.2017.05.016zbMath1372.05216arXiv1403.5702MaRDI QIDQ2402366

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

Publication date: 7 September 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.5702

zbMATH Keywords

dynamic programming; outerplanar graphs; completion problems; polynomial-time algorithms; diameter improvement

Mathematics Subject Classification ID

90C39: Dynamic programming

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Augmenting Geometric Graphs with Matchings, A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Augmenting graphs to minimize the diameter
• Graph minors. XX: Wagner's conjecture
• 2-connecting outerplanar graphs without blowing up the pathwidth
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Quickly excluding a forest
• How to decrease the diameter of triangle-free graphs
• On the complexity of DNA physical mapping
• Graph minors. XIII: The disjoint paths problem
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Parametrized complexity theory.
• Design networks with bounded pairwise distance
• Augmenting Outerplanar Graphs to Meet Diameter Requirements
• Planar Disjoint-Paths Completion
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Decreasing the diameter of bounded degree graphs
• Augmenting Outerplanar Graphs
• Parameterized Algorithms
• Mixed covering of trees and the augmentation problem with odd diameter constraints