2011/08/01 by Sven Herrmann, Jack Koolen, Jack H. Koolen +8
Computer Science · Mathematics · #05C12 #30L05 #52B99 #54E99 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Metric Geometry (math.MG) #Topological and Geometric Data Analysis #math.CO #math.MG #msc:05C12 #msc:30L05 #msc:52B99 #msc:54E99
paper · pdf · doi:10.48550/arxiv.1108.0290
18 pages, 1 figure
openalex publication_date 2011/08/01 · arxiv created 2015/02/07 · arxiv updated 2015/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A realisation of a metric d on a finite set X is a weighted graph (G,w) whose vertex set contains X such that the shortest-path distance between elements of X considered as vertices in G is equal to d. Such a realisation (G,w) is called optimal if the sum of its edge weights is minimal over all such realisations. Optimal realisations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. In [Adv. in Math. 53, 1984, 321-402] A.~Dress showed that the optimal realisations of a metric d are closely related to a certain polytopal complex that can be canonically associated to d called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of d must always contain an optimal realisation as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally"=decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realisations of two-dimensional totally-decomposable metrics.