Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.disc.2012.02.003
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. https://doi.org/10.1016/j.disc.2012.02.003 | 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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/103429 | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.