A polynomial-time algorithm for outerplanar diameter improvement
From MaRDI portal
Publication:2402366
DOI10.1016/j.jcss.2017.05.016zbMath1372.05216arXiv1403.5702OpenAlexW2723105293MaRDI 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
dynamic programmingouterplanar graphscompletion problemspolynomial-time algorithmsdiameter improvement
Dynamic programming (90C39) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Augmenting Geometric Graphs with Matchings
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A polynomial-time algorithm for outerplanar diameter improvement
