Fast Algorithms for Diameter-Optimally Augmenting Paths

We consider the problem of augmenting a graph with

$$n$$

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)$$

O

(

n

log

3

n

)

time. We also present an algorithm that computes a

$$(1+\varepsilon )$$

(

1

+

ε

)

-approximation in

$$O(n + 1/\varepsilon ^3)$$

O

(

n

+

1

/

ε

3

)

time for paths in

$${\mathbb {R}}^{d}$$

R

d

, where

$$d$$

d

is a constant.