A Linear-Time Algorithm for Radius-Optimally Augmenting Paths in a Metric Space

Christopher Johnson, Haitao Wang

Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ to minimize the radius of the resulting graph. Previously, a…