A Polynomial-Time Algorithm for Outerplanar Diameter Improvement
DOI10.1007/978-3-319-20297-6_9zbMath1464.68280OpenAlexW2962804000MaRDI QIDQ3194712
Ignasi Sau, Christophe Paul, Dimitrios M. Thilikos, Daniel Gonçalves, Mathias Weller, Nathann Cohen, Eun Jung Kim
Publication date: 20 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-20297-6_9
dynamic programmingouterplanar graphscompletion problemspolynomial-time algorithmsdiameter improvement
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- 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
- How to decrease the diameter of triangle-free graphs
- On the complexity of DNA physical mapping
- Graph minors. XIII: The disjoint paths problem
- Parametrized complexity theory.
- Design networks with bounded pairwise distance
- Augmenting Outerplanar Graphs to Meet Diameter Requirements
- Planar Disjoint-Paths Completion
- A Polynomial-Time Algorithm for Outerplanar Diameter Improvement
- 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
- Mixed covering of trees and the augmentation problem with odd diameter constraints
This page was built for publication: A Polynomial-Time Algorithm for Outerplanar Diameter Improvement
