Improved approximability and non-approximability results for graph diameter decreasing problems
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 4137792 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 3212735 (Why is no real title available?)
- A textbook of graph theory
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Approximation algorithms for combinatorial problems
- Augmenting forests to meet odd diameter requirements
- Augmenting trees to meet biconnectivity and diameter constraints
- Bounded-diameter minimum-cost graph problems
- Clustering to minimize the maximum intercluster distance
- Decreasing the diameter of bounded degree graphs
- Decreasing the diameter of cycles
- Design networks with bounded pairwise distance
- Diameter bounds for altered graphs
- Diameter increase caused by edge deletion
- Graph Classes: A Survey
- How to decrease the diameter of triangle-free graphs
- Location on Tree Networks: P-Centre and n-Dispersion Problems
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- Minimizing the diameter of a network using shortcut edges
- Mixed covering of trees and the augmentation problem with odd diameter constraints
- On the computational complexity of centers locating in a graph
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- The complexity of designing a network with minimum diameter
Cited in
(29)- 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
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- Improved approximability and non-approximability results for graph diameter decreasing 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
- Augmenting weighted graphs to establish directed point-to-point connectivity
- Almost optimal algorithms for diameter-optimally augmenting trees
- On the hardness of problems around s-clubs on split graphs
- 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
- Bicriteria approximation for minimum dilation graph augmentation
- A polynomial-time algorithm for outerplanar diameter improvement
- A polynomial-time algorithm for outerplanar diameter improvement
- Almost optimal algorithms for diameter-optimally augmenting trees
- Shortcutting directed and undirected networks with a degree constraint
- Augmenting graphs to minimize the radius
- Shortcuts for the circle
- Shortcuts for the circle
- Finding diameter-reducing shortcuts in trees
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)
