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+ε)-approximation in O(n + 1/ε~3) time for paths in R~d, where d is a constant.
展开▼
