A linear-time algorithm for radius-optimally augmenting paths in a metric space

DOI10.1016/J.COMGEO.2021.101759MaRDI QIDQ5918103zbMATH OpenOpenAlexFDO

Authors

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

zbMATH Keywords

augmenting pathsmetric spaceminimizing radiuspath graphsshortcuts

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ to minimize the radius of the resulting graph. Previously, a similar problem for minimizing the diameter of the graph was solved in $O(nlogn)$ time. To the best of our knowledge, the problem of minimizing the radius has not been studied before. In this paper, we present an $O(n)$ time algorithm for the problem, which is optimal.

Recommendations

• A linear-time algorithm for discrete radius optimally augmenting paths in a metric space
• Algorithms for radius-optimally augmenting trees in a metric space
• Fast algorithms for diameter-optimally augmenting paths

Cites work

• A near-optimal algorithm for finding an optimal shortcut of a tree
• Almost optimal algorithms for diameter-optimally augmenting trees
• An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Augmenting outerplanar graphs to meet diameter requirements
• Decreasing the diameter of bounded degree graphs
• Diameter increase caused by edge deletion
• Fast algorithms for diameter-optimally augmenting paths
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• New Results on the Complexity of p-Centre Problems
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Shortcuts for the circle
• The parametric complexity of graph diameter augmentation

Cited in

(7)

• Almost optimal algorithms for diameter-optimally augmenting trees
• A linear-time algorithm for discrete radius optimally augmenting paths in a metric space
• A linear-time algorithm for radius-optimally augmenting paths in a metric space
• Algorithms for radius-optimally augmenting trees in a metric space
• Finding diameter-reducing shortcuts in trees
• Finding diameter-reducing shortcuts in trees
• Bicriteria approximation for minimum dilation graph augmentation

This page was built for publication: A linear-time algorithm for radius-optimally augmenting paths in a metric space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918103)