Optimal Embedding Into Star Metrics

Details Optimal Embedding Into Star Metrics Optimal Embedding Into Star Metrics

2009-05-03

arxiv.org/abs/0905.0283v1

Computer Science

Data Structures and Algorithms

12 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimal Embedding Into Star Metrics 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 Optimal Embedding Into Star Metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Embedding Into Star Metrics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-109339