Improved approximability and non-approximability results for graph diameter decreasing problems
DOI10.1016/J.TCS.2011.05.014zbMATH Open1234.68127OpenAlexW1973394376MaRDI QIDQ764323FDOQ764323
Authors: D. Bilò, Luciano Gualà, Guido Proietti 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12)
Cites Work
- Approximation algorithms for combinatorial problems
- Bounded-diameter minimum-cost graph problems
- Graph Classes: A Survey
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- Augmenting trees to meet biconnectivity and diameter constraints
- Title not available (Why is that?)
- Diameter bounds for altered graphs
- Clustering to minimize the maximum intercluster distance
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Title not available (Why is that?)
- A textbook of graph theory
- Diameter increase caused by edge deletion
- The complexity of designing a network with minimum diameter
- Design networks with bounded pairwise distance
- Augmenting forests to meet odd diameter requirements
- Minimizing the diameter of a network using shortcut edges
- Decreasing the diameter of cycles
- Decreasing the diameter of bounded degree graphs
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- On the computational complexity of centers locating in a graph
- Location on Tree Networks: P-Centre and n-Dispersion Problems
- How to decrease the diameter of triangle-free graphs
- Title not available (Why is that?)
- Mixed covering of trees and the augmentation problem with odd diameter constraints
Cited In (26)
- Algorithms for radius-optimally augmenting trees in a metric space
- Algorithms for radius-optimally augmenting trees in a metric space
- Fast algorithms for diameter-optimally augmenting paths
- On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph
- 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
- Augmenting outerplanar graphs to meet diameter requirements
- Fast algorithms for diameter-optimally augmenting paths and trees
- A linear-time algorithm for radius-optimally augmenting paths in a metric space
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- A linear-time algorithm for discrete radius optimally augmenting paths in a metric space
- Reducing the diameter of a unit disk graph via node addition
- Almost optimal algorithms for diameter-optimally augmenting trees
- Augmenting weighted graphs to establish directed point-to-point connectivity
- Finding diameter-reducing shortcuts in trees
- Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approaches
- Improving the betweenness centrality of a node by adding links
- Online and Approximate Network Construction from Bounded Connectivity Constraints
- Using shortcut edges to maximize the number of triangles in graphs
- A polynomial-time algorithm for outerplanar diameter improvement
- A polynomial-time algorithm for outerplanar diameter improvement
- Almost optimal algorithms for diameter-optimally augmenting trees
- Augmenting graphs to minimize the radius
- Shortcutting directed and undirected networks with a degree constraint
- Shortcuts for the circle
- Shortcuts for the circle
This page was built for publication: Improved approximability and non-approximability results for graph diameter decreasing problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764323)
