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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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) Published
Resource type
Text
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
Identifiers
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: 2017-12-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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 230 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf