A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space

DOI10.1142/S0218195920500089MaRDI QIDQ5012871

No author found.

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

path graphsaugmenting pathsdiscrete radius

Mathematics Subject Classification ID

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

Related Items (1)

Algorithms for radius-optimally augmenting trees in a metric space

Cites Work

• 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 Diameter-Optimally Augmenting Paths
• Diameter increase caused by edge deletion
• Decreasing the diameter of bounded degree graphs
• A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree
• Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
• An improved algorithm for diameter-optimally augmenting paths in a metric space
• A linear-time algorithm for radius-optimally augmenting paths in a metric space
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space