Elisabeth Gassner

Title:
Inverse maxian problems with variable edge lengths on a tree

Abstract:
We consider the problem of modifying the lengths of the edges in a tree at minimum cost such that a prespecified set of vertices becomes a p-maxian with respect to the new edge lengths. A transformation of the inverse p-maxian problem on a tree to a minimum cost flow circulation problem is given which solved the original problem in O(n log^2 n) time if p=1 and in O(n^2 log^2 n) time if p=2. The case of p=2 can directly be adapted to solve the problem for p>2. Moreover, it is shown that the inverse 2-maxian problem with variable edge lengths and the inverse diameter problem are equivalent on a tree.