On optimal embeddings of metrics in graphs (Q794666)

A graph \(G=(V,E,w)\) with vertex set V, edge set E and the weighting function \(w:\quad E\to R^+\) is said to realize a metric (M,d) if M is a subset of V and if \(d(a,b)=d_ G(a,b)\) for all elements a, b of \(M(d_ G(a,b)\) denotes the distance between vertices a and b in the graph G). A realization G of (M,d) is called optimal if the sum of all edge lengths of G, denoted w(G) is minimal among all realizations of (M,d). The authors of the paper under review prove first that every finite metric (M,d) has an optimal realization by a graph. Then they investigate cases in which the optimal realization is unique. In a next section there are given examples of optimal realizations. In a fifth section of the paper the authors give a shorter proof of a theorem published first by the author and \textit{E. Stockiĭ} [Sibir. Mat. Zh. 13, 558-565 (1972; Zbl 0238.05121)] and give a characterization of tree-realizable metrics.