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

Direct link
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
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: 2013-03-04Bibliographically 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

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: 180 hits
ReferencesLink to record
Permanent link

Direct link