  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 algorithms for the cases when (i) the
input graph is a path, running in O(n \log^3 n) time, and (ii) the input graph
is a tree, running in O(n^2 \log n) time. We also present an algorithm that
computes a (1+\eps)-approximation in O(n + 1/\eps^3) time, for paths in R^d,
where d is a constant.
