Improved approximability and non-approximability results for graph diameter decreasing problems
From MaRDI portal
Publication:764323
DOI10.1016/j.tcs.2011.05.014zbMath1234.68127OpenAlexW1973394376MaRDI QIDQ764323
Guido Proietti, Davide Bilò, Luciano Gualà
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.014
Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (25)
Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ Algorithms for radius-optimally augmenting trees in a metric space ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ Improving the Betweenness Centrality of a Node by Adding Links ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ Almost optimal algorithms for diameter-optimally augmenting trees ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approaches ⋮ Augmenting graphs to minimize the radius ⋮ Online and Approximate Network Construction from Bounded Connectivity Constraints ⋮ Finding diameter-reducing shortcuts in trees ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ Algorithms for radius-optimally augmenting trees in a metric space ⋮ Augmenting graphs to minimize the diameter ⋮ Shortcuts for the circle ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ An improved algorithm for diameter-optimally augmenting paths in a metric space ⋮ Unnamed Item ⋮ Using shortcut edges to maximize the number of triangles in graphs ⋮ A linear-time algorithm for radius-optimally augmenting paths in a metric space ⋮ Unnamed Item ⋮ A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space ⋮ Augmenting Outerplanar Graphs to Meet Diameter Requirements ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ Reducing the diameter of a unit disk graph via node addition
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Clustering to minimize the maximum intercluster distance
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- Approximation algorithms for combinatorial problems
- How to decrease the diameter of triangle-free graphs
- Augmenting trees to meet biconnectivity and diameter constraints
- Bounded-diameter minimum-cost graph problems
- Augmenting forests to meet odd diameter requirements
- Design networks with bounded pairwise distance
- Minimizing the Diameter of a Network Using Shortcut Edges
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- Diameter increase caused by edge deletion
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- On the computational complexity of centers locating in a graph
- The complexity of designing a network with minimum diameter
- Location on Tree Networks: P-Centre and n-Dispersion Problems
- Graph Classes: A Survey
- Decreasing the diameter of cycles
- Decreasing the diameter of bounded degree graphs
- Diameter bounds for altered graphs
- A textbook of graph theory
- Mixed covering of trees and the augmentation problem with odd diameter constraints
This page was built for publication: Improved approximability and non-approximability results for graph diameter decreasing problems
