A strongly polynomial algorithm for the inverse shortest arborescence problem

In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is, given a directed graph G and a set of nonnegative costs on its arcs, we need to modify those costs as little as possible to ensure that T, a given upsilon(1)-arborescence of G, is the shortest one. It is found that only the cost of T needs modifying. An O(n(3)) combinatorial algorithm is then proposed. This algorithm also gives an optimal solution to the inverse weighted shortest path problem. (C) 1998 Elsevier Science B.V. All rights reserved.