Abstract
A realization of a metric on a finite set is a weighted graph whose vertex set contains such that the shortestpath distance between elements of considered as vertices in is equal to . Such a realization is called optimal if the sum of its edge weights is minimal over all such realizations. Optimal realizations always exist, although it is NPhard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. A. Dress (1984) showed that the optimal realizations of a metric are closely related to a certain polytopal complex that can be canonically associated to called its tightspan. Moreover, he conjectured that the (weighted) graph consisting of the zero and onedimensional faces of the tightspan of must always contain an optimal realization 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 totallydecomposable metrics whose tightspan has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realizations of twodimensional totallydecomposable metrics.
Original language  English 

Pages (fromto)  1289–1299 
Number of pages  11 
Journal  Discrete Mathematics 
Volume  338 
Issue number  8 
Early online date  16 Mar 2015 
DOIs  
Publication status  Published  6 Aug 2015 
Profiles

Vincent Moulton
 School of Computing Sciences  Professor in Computational Biology
 Norwich Epidemiology Centre  Member
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Taoyang Wu
 School of Computing Sciences  Lecturer in Computing Sciences
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research