Optimal Embedding Into Star Metrics

Simple item page
dc.creatorEppstein, David
dc.creatorWortman, Kevin A.
dc.date2009-05-03
dc.date.accessioned2026-07-07T13:11:22Z
dc.date.available2026-07-07T13:11:22Z
dc.descriptionWe 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.
dc.description12 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/0905.0283
dc.identifierhttp://arxiv.org/abs/0905.0283
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/229263
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleOptimal Embedding Into Star Metrics
dc.typetext

Files

Collections

arXiv