Augmenting Outerplanar Graphs to Meet Diameter Requirements
From MaRDI portal
Publication:2862552
DOI10.1002/jgt.21719zbMath1276.05034OpenAlexW2148734039MaRDI QIDQ2862552
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
diameterouterplanar graphsundirected graphpartial 2-treesconstant factor approximation algorithmgraph augmentation problem
Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)
Related Items (10)
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
This page was built for publication: Augmenting Outerplanar Graphs to Meet Diameter Requirements
