An algorithm for computing cutpoints in finite metric spaces

Dress, Andreas W. M., Huber, Katharina T., Koolen, Jacobus, Moulton, Vincent and Spillner, Andreas (2010) An algorithm for computing cutpoints in finite metric spaces. Journal of Classification, 27 (2). pp. 158-172.

Full text not available from this repository. (Request a copy)

Abstract

The theory of the tight span, a cell complex that can be associated to every metric D, offers a unifying view on existing approaches for analyzing distance data, in particular for decomposing a metric D into a sum of simpler metrics as well as for representing it by certain specific edge-weighted graphs, often referred to as realizations of D. Many of these approaches involve the explicit or implicit computation of the so-called cutpoints of (the tight span of) D, such as the algorithm for computing the “building blocks” of optimal realizations of D recently presented by A. Hertz and S. Varone. The main result of this paper is an algorithm for computing the set of these cutpoints for a metric D on a finite set with n elements in O(n3) time. As a direct consequence, this improves the run time of the aforementioned O(n6)-algorithm by Hertz and Varone by “three orders of magnitude”.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018)
Depositing User:	Vishal Gautam
Date Deposited:	11 Mar 2011 16:16
Last Modified:	06 Feb 2025 01:59
URI:	https://ueaeprints.uea.ac.uk/id/eprint/22427
DOI:	10.1007/s00357-010-9055-7

Actions (login required)

View Item