Optimal realizations of two-dimensional, totally-decomposable metrics
2015 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 338, no 8, 1289-1299 p.Article in journal (Refereed) PublishedText
A realization 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 realization (G, w) is called optimal if the sum of its edge weights is minimal over all such realizations. Optimal realizations 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. A. Dress (1984) showed that the optimal realizations of a metric dare 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 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 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 realizations of two-dimensional totally-decomposable metrics. (C) 2015 Elsevier B.V. All rights reserved.
Place, publisher, year, edition, pages
2015. Vol. 338, no 8, 1289-1299 p.
Optimal realizations, Totally-decomposable metrics, Tight-span, Manhattan network problem, Buneman complex
IdentifiersURN: urn:nbn:se:uu:diva-270646DOI: 10.1016/j.disc.2015.02.008ISI: 000365146100003OAI: oai:DiVA.org:uu-270646DiVA: diva2:890210