Abstract:
We consider the following problem: given a collection of n sites separated by distances obeying the triangle inequality, create a star (tree of depth 1) whose root is a new center site and whose leaves are the input sites, such that the dilation of the star is minimal. The problem amounts to computing a weight for each of the n edges from the root to the leaves, such that all the weights in the star obey the triangle inequality. This talk will describe an O(n3)-time algorithm for computing the optimal dilation value, which is a significant component of an algorithm that computes the edge weights.
(Joint work in progress with David Eppstein.)