An Algorithm for Computing Cutpoints in Finite Metric Spaces
SCIE
SSCI
AHCI
SCOPUS
- Title
- An Algorithm for Computing Cutpoints in Finite Metric Spaces
- Authors
- Dress, A; Huber, K; Koolen, J; Moulton, V; Spillner, A
- Date Issued
- 2010-09
- Publisher
- SPRINGER
- 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".
- Keywords
- Metric; Cutpoint; Realization; Tight span; Decomposition; Block; BLOCK REALIZATIONS; PARTITION PROBLEM; CUT POINTS
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/25566
- DOI
- 10.1007/S00357-010-9055-7
- ISSN
- 0176-4268
- Article Type
- Article
- Citation
- JOURNAL OF CLASSIFICATION, vol. 27, no. 2, page. 158 - 172, 2010-09
- 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.