Optimal Embedding Into Star Metrics

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We present an O(n^3 log^2 n)-time algorithm for the following problem: given a finite metric space X, create a star-topology network with the points of X as its leaves, such that the distances in the star are at least as large as in X, with minimum dilation. As part of our algorithm, we solve in the same time bound the parametric negative cycle detection problem: given a directed graph with edge weights that are increasing linear functions of a parameter lambda, find the smallest value of lambda such that the graph contains no negative-weight cycles.
12 pages, 3 figures

Keywords

Data Structures and Algorithms, F.2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/229263

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0905.0283
 http://arxiv.org/abs/0905.0283

Collections

arXiv