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

DOI10.1142/S0218195920500089MaRDI QIDQ5012871zbMATH OpenFDO

Authors

Publication date 26 November 2021

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.14093

zbMATH Keywords

augmenting pathsdiscrete radiuspath graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A linear-time algorithm for 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 linear-time algorithm for radius-optimally augmenting paths in a metric space
• A near-optimal algorithm for finding an optimal shortcut of a tree
• Almost optimal algorithms for diameter-optimally augmenting trees
• 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 diameter-optimally augmenting paths and trees
• 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
• 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

(6)

• A linear-time algorithm for 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
• Augmenting graphs to minimize the radius
• Bicriteria approximation for minimum dilation graph augmentation
• Algorithms for radius-optimally augmenting trees in a metric space

This page was built for publication: A linear-time algorithm for discrete 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 Q5012871)