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
Injective optimal realizations of finite metric spaces
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2012 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 10, 1602-1610 p.Article in journal (Refereed) Published
Abstract [en]

A realization of a finite metric space (X, d) is a weighted graph (G, w) whose vertex set contains X such that the distances between the elements of X in G correspond to those given by d. Such a realization is called optimal if it has minimal total edge weight. Optimal realizations have applications in fields such as phylogenetics, psychology, compression software and Internet tomography. Given an optimal realization (G, w) of (X, d), there always exist certain "proper" maps from the vertex set of G into the so-called tight span of d. In [A. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. Math. 53 (1984) 321-402], Dress conjectured that any such map must be injective. Although this conjecture was recently disproven, in this paper we show that it is possible to characterize those optimal realizations (G, w) for which certain generalizations of proper maps - that map the geometric realization of (G, w) into the tight span instead of its vertex set - must always be injective. We also prove that these "injective" optimal realizations always exist, and show how they may be constructed from non-injective ones. Ultimately it is hoped that these results will contribute towards developing new ways to compute optimal realizations from tight spans.

Place, publisher, year, edition, pages
2012. Vol. 312, no 10, 1602-1610 p.
Keyword [en]
Finite metric spaces, Optimal realizations, Tight span, Proper maps
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-174900DOI: 10.1016/j.disc.2012.02.003ISI: 000303288500003OAI: oai:DiVA.org:uu-174900DiVA: diva2:529535
Available from: 2012-05-30 Created: 2012-05-30 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Analysis and Applied Mathematics
In the same journal
Discrete Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 380 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