Tools
Tools
Dress, Andreas W. M., Huber, Katharina T., Koolen, Jacobus, Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435 and Spillner, Andreas
(2010)
An algorithm for computing cutpoints in finite metric spaces.
Journal of Classification, 27 (2).
pp. 158-172.
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 |
| Depositing User: | Vishal Gautam |
| Date Deposited: | 11 Mar 2011 16:16 |
| Last Modified: | 15 Dec 2022 01:28 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/22427 |
| DOI: | 10.1007/s00357-010-9055-7 |
Actions (login required)
 |
View Item |