An algorithm for computing cutpoints in finite metric spaces

Details An algorithm for computing cutpoints in finite metric spaces An algorithm for computing cutpoints in finite metric spaces

2009-10-13

arxiv.org/abs/0910.2317v1

Computer Science

Data Structures and Algorithms

17 pages, 1 eps-figure

Scientific paper

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(n^3)$ time. As a direct consequence, this improves the run time of the aforementioned $O(n^6)$-algorithm by Hertz and Varone by ``three orders of magnitude''.

Affiliated with

Also associated with

No associations

Rating

An algorithm for computing cutpoints in finite metric spaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An algorithm for computing cutpoints in finite metric spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An algorithm for computing cutpoints in finite metric spaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-640355