A polynomial-time algorithm for outerplanar diameter improvement

DOI10.1007/978-3-319-20297-6_9MaRDI QIDQ3194712zbMATH OpenOpenAlexFDO

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

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

zbMATH Keywords

completion problemsdiameter improvementdynamic programmingouterplanar graphspolynomial-time algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Dynamic programming (90C39)

Recommendations

• A polynomial-time algorithm for outerplanar diameter improvement
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
• Augmenting outerplanar graphs to meet diameter requirements
• Approximation of pathwidth of outerplanar graphs
• scientific article; zbMATH DE number 2044933

Cites work

• 2-connecting outerplanar graphs without blowing up the pathwidth
• A characterisation of eccentric sequences of maximal outerplanar graphs
• A polynomial-time algorithm for outerplanar diameter improvement
• Augmenting Outerplanar Graphs
• Augmenting outerplanar graphs to meet diameter requirements
• Computing the Minimum Fill-In is NP-Complete
• Decreasing the diameter of bounded degree graphs
• Design networks with bounded pairwise distance
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• How to decrease the diameter of triangle-free graphs
• scientific article; zbMATH DE number 5485472 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Mixed covering of trees and the augmentation problem with odd diameter constraints
• On the complexity of DNA physical mapping
• Parametrized complexity theory.
• Planar disjoint-paths completion
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Cited in

(3)

• A polynomial-time algorithm for outerplanar diameter improvement
• A polynomial-time algorithm for outerplanar diameter improvement
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem

This page was built for publication: A polynomial-time algorithm for outerplanar diameter improvement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194712)