Please use this identifier to cite or link to this item:
Title: Injective optimal realizations of finite metric spaces
Authors: Koolen, J.H.
Lesser, A.
Moulton, V.
Wu, T. 
Keywords: Finite metric spaces
Optimal realizations
Proper maps
Tight span
Issue Date: 28-May-2012
Citation: Koolen, J.H., Lesser, A., Moulton, V., Wu, T. (2012-05-28). Injective optimal realizations of finite metric spaces. Discrete Mathematics 312 (10) : 1602-1610. ScholarBank@NUS Repository.
Abstract: 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) 321402], 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 mapsthat map the geometric realization of (G,w) into the tight span instead of its vertex setmust 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. © 2012 Elsevier B.V. All rights reserved.
Source Title: Discrete Mathematics
ISSN: 0012365X
DOI: 10.1016/j.disc.2012.02.003
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Sep 28, 2020


checked on Jul 2, 2019

Page view(s)

checked on Sep 26, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.