uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Optimal realizations of two-dimensional, totally-decomposable metrics
Univ E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England..
Univ Sci & Technol China, Sch Math Sci, Wen Tsun Wu Key Lab, CAS, Hefei, Peoples R China..
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
Univ E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England..
Show others and affiliations
2015 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 338, no 8, 1289-1299 p.Article in journal (Refereed) PublishedText
Abstract [en]

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.
Keyword [en]
Optimal realizations, Totally-decomposable metrics, Tight-span, Manhattan network problem, Buneman complex
National Category
Discrete Mathematics
URN: urn:nbn:se:uu:diva-270646DOI: 10.1016/j.disc.2015.02.008ISI: 000365146100003OAI: oai:DiVA.org:uu-270646DiVA: diva2:890210
Available from: 2016-01-01 Created: 2016-01-01 Last updated: 2016-01-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Department of Mathematics
In the same journal
Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 63 hits
ReferencesLink to record
Permanent link

Direct link