Augmenting Outerplanar Graphs to Meet Diameter Requirements

DOI10.1002/jgt.21719zbMath1276.05034OpenAlexW2148734039MaRDI QIDQ2862552

Toshimasa Ishii

Publication date: 15 November 2013

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21719

zbMATH Keywords

diameterouterplanar graphsundirected graphpartial 2-treesconstant factor approximation algorithmgraph augmentation problem

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)

Related Items

Fast Algorithms for Diameter-Optimally Augmenting Paths, A Polynomial-Time Algorithm for Outerplanar Diameter Improvement, Almost optimal algorithms for diameter-optimally augmenting trees, A polynomial-time algorithm for outerplanar diameter improvement, Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees, An improved algorithm for diameter-optimally augmenting paths in a metric space, Unnamed Item, A linear-time algorithm for radius-optimally augmenting paths in a metric space, A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space, Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees

Cites Work

• Unnamed Item
• Improved approximability and non-approximability results for graph diameter decreasing problems
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• How to decrease the diameter of triangle-free graphs
• Augmenting trees to meet biconnectivity and diameter constraints
• Augmenting forests to meet odd diameter requirements
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Diameter increase caused by edge deletion
• Dually Chordal Graphs
• Decreasing the diameter of bounded degree graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Mixed covering of trees and the augmentation problem with odd diameter constraints