A linear-time algorithm for radius-optimally augmenting paths in a metric space
From MaRDI portal
Publication:5918103
DOI10.1016/j.comgeo.2021.101759zbMath1473.05293arXiv1904.12061OpenAlexW2942194578MaRDI QIDQ5918103
No author found.
Publication date: 16 September 2021
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.12061
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Almost optimal algorithms for diameter-optimally augmenting trees ⋮ Finding diameter-reducing shortcuts in trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Augmenting graphs to minimize the diameter
- 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
- Minimizing the continuous diameter when augmenting a tree with a shortcut
- The parametric complexity of graph diameter augmentation
- Augmenting Outerplanar Graphs to Meet Diameter Requirements
- Fast Algorithms for Finding Nearest Common Ancestors
- Fast Algorithms for Diameter-Optimally Augmenting Paths
- New Results on the Complexity of p-Centre Problems
- Diameter increase caused by edge deletion
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Decreasing the diameter of bounded degree graphs
- A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree
- An O(n log n)-Time Algorithm for the k-Center Problem in Trees
- An improved algorithm for diameter-optimally augmenting paths in a metric space
This page was built for publication: A linear-time algorithm for radius-optimally augmenting paths in a metric space
