Fast Algorithms for Diameter-Optimally Augmenting Paths

We consider the problem of augmenting a graph with \(n\) vertices embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present an exact algorithm for the cases when the input graph is a path that runs in \(O(n \log ^3 n)\) time. We also present an algorithm that computes a \((1+\varepsilon )\)-approximation in \(O(n + 1/\varepsilon ^3)\) time for paths in \({\mathbb {R}}^{d}\), where \(d\) is a constant.