Optimal realisations of two-dimensional, totally split-decomposable metrics

Herrmann, Sven, Koolen, Jack H., Lesser, Alice, Moulton, Vincent and Wu, Taoyang (2015) Optimal realisations of two-dimensional, totally split-decomposable metrics. Discrete Mathematics, 338 (8). 1289–1299. ISSN 0012-365X

Preview

PDF (2-decomp-final) - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (378kB) | Preview

Abstract

A realization of a metric on a finite set is a weighted graph whose vertex set contains such that the shortest-path distance between elements of considered as vertices in is equal to . Such a realization 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 are closely related to a certain polytopal complex that can be canonically associated to called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of 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.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Centres > Centre for Ecology, Evolution and Conservation Faculty of Science > Research Groups > Data Science and AI
Depositing User:	Pure Connector
Date Deposited:	22 Apr 2015 11:28
Last Modified:	15 Oct 2025 11:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/53242
DOI:	10.1016/j.disc.2015.02.008

Downloads

Actions (login required)

View Item