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 log3 n) time. We also present an algorithm that computes a (1+ε)-approximation in O(n+1/ε3) time for paths in Rd, where d is a constant.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-662-47672-7_55
Große, U. (Ulrike), Gudmundsson, J. (Joachim), Knauer, C. (Christian), Smid, M, & Stehn, F. (Fabian). (2015). Fast algorithms for diameter-optimally augmenting paths. doi:10.1007/978-3-662-47672-7_55