by Ulrike Große,
Christian Knauer,
Fabian Stehn, Joachim Gudmundsson, Michiel Smid
Abstract:
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 for paths that computes a (1 + 𝜀)-approximation in O(n + 1/𝜀^3) time.
Reference:
Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees (Ulrike Große, Christian Knauer, Fabian Stehn, Joachim Gudmundsson, Michiel Smid), In International Journal of Foundations of Computer Science, volume 30, 2019.
Bibtex Entry:
@article{journals:10.1142/S0129054119500060,
author = {Große, Ulrike and Knauer, Christian and Stehn, Fabian and Gudmundsson, Joachim and Smid, Michiel},
title = {Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees},
journal = {International Journal of Foundations of Computer Science},
volume = {30},
number = {02},
pages = {293-313},
year = {2019},
doi = {10.1142/S0129054119500060},
URL = { https://doi.org/10.1142/S0129054119500060},
eprint = {https://doi.org/10.1142/S0129054119500060},
abstract = { 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 for paths that computes a (1 + 𝜀)-approximation in O(n + 1/𝜀^3) time. }
}