Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees

We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algor...