An algorithm for computing cutpoints in finite metric spaces TeX Export

@article{citeulike:5938312, 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(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''.}, archivePrefix = {arXiv}, author = {Dress, A. and Huber, K. T. and Koolen, J. and Moulton, V. and Spillner, A.}, citeulike-article-id = {5938312}, citeulike-linkout-0 = {http://arxiv.org/abs/0910.2317}, citeulike-linkout-1 = {http://arxiv.org/pdf/0910.2317}, day = {13}, eprint = {0910.2317}, keywords = {discrete, finite, metric-space}, month = {Oct}, posted-at = {2009-11-06 15:49:37}, priority = {2}, title = {An algorithm for computing cutpoints in finite metric spaces}, url = {http://arxiv.org/abs/0910.2317}, year = {2009} }

TY - JOUR ID - citeulike:5938312 L3 - citeulike-article-id:5938312 N2 - 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''. TI - An algorithm for computing cutpoints in finite metric spaces KW - discrete KW - finite KW - metric-space AU - Dress, A AU - Huber, KT AU - Koolen, J AU - Moulton, V AU - Spillner, A PY - 2009/Oct/13/ UR - http://arxiv.org/abs/0910.2317 ER -