Finding Diameter-Reducing Shortcuts in Trees

Davide Bilò, Luciano Gualà, Stefano Leucci +1

In the \emph{$k$-Diameter-Optimally Augmenting Tree Problem} we are given a tree $T$ of $n$ vertices as input. The tree is embedded in an unknown \emph{metric} space and we have un…