Fast algorithms for diameter-optimally augmenting paths and trees
From MaRDI portal
Publication:5384465
Abstract: We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n log^3 n) time, and (ii) the input graph is a tree, running in O(n^2 log n) time. We also present an algorithm that computes a (1+eps)-approximation in O(n + 1/eps^3) time, for paths in R^d, where d is a constant.
Recommendations
Cites work
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 6792403 (Why is no real title available?)
- A near-optimal algorithm for finding an optimal shortcut of a tree
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Augmenting outerplanar graphs to meet diameter requirements
- Augmenting the connectivity of planar and geometric graphs
- Augmenting trees to meet biconnectivity and diameter constraints
- Bounded-diameter minimum-cost graph problems
- Combinatorial Optimization with Rational Objective Functions
- Computational geometry. Algorithms and applications.
- Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
- Computing the dilation of edge-augmented graphs in metric spaces
- Decreasing the diameter of bounded degree graphs
- Design networks with bounded pairwise distance
- Diameter bounds for altered graphs
- Diameter increase caused by edge deletion
- Euclidean chains and their shortcuts
- Fast algorithms for diameter-optimally augmenting paths
- How to decrease the diameter of triangle-free graphs
- Improved approximability and non-approximability results for graph diameter decreasing problems
- Improving the Stretch Factor of a Geometric Network by Edge Augmentation
- Minimizing the continuous diameter when augmenting a tree with a shortcut
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- Parametric search made practical
- The parametric complexity of graph diameter augmentation
Cited in
(14)- Upgrading trees under diameter and budget constraints
- Algorithms for radius-optimally augmenting trees in a metric space
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- Algorithms for radius-optimally augmenting trees in a metric space
- Fast algorithms for diameter-optimally augmenting paths
- Shortest augmenting paths for online matchings on trees
- 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
- Almost optimal algorithms for diameter-optimally augmenting trees
- Algorithms and Data Structures
- Finding diameter-reducing shortcuts in trees
- Minimizing the continuous diameter when augmenting a tree with a shortcut
- Almost optimal algorithms for diameter-optimally augmenting trees
- Augmenting graphs to minimize the radius
This page was built for publication: Fast algorithms for diameter-optimally augmenting paths and trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384465)
