We consider the problem of augmenting an n-vertex graph embedded in a metricspace, by inserting one additional edge in order to minimize the diameter ofthe resulting graph. We present exact algorithms for the cases when (i) theinput graph is a path, running in O(n log^3 n) time, and (ii) the input graphis a tree, running in O(n^2 log n) time. We also present an algorithm thatcomputes a (1+eps)-approximation in O(n + 1/eps^3) time, for paths in R^d,where d is a constant.
展开▼
