Steiner points in tree metrics don't (really) help (Q2768295)

Each edge-weighted graph is a metric space on the set of its vertices defining the shortest-path distance according to the edge-weights. The paper shows: For any edge-weighted tree \(T= (R\cup S,E,w: E\to R^+)\) with metric \(d_T\) there is an edge-weighted tree \(T'= (R, E',w': E'\to R^+)\) such that \(d_T(u, v)\leq d_{T'}\) \((u,v)\leq 8\cdot d_T(u, v)\) for any two vertices \(u\), \(v\) in \(R\). A linear time algorithm to compute \(T'\) from \(T\) is given.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].