A faster algorithm for the inverse spanning tree problem

In this paper, we consider the inverse spanning tree problem. Given an undirected graph G(0) = (N-0, A(0)) with n nodes, m arcs, an are cost vector c, and a spanning tree T-0, the inverse spanning tree problem is to perturb the are cost vector c to a vector d so that T-0 is a minimum spanning tree with respect to the cost vector d and the cost of perturbation given by \d - c\ = Sigma((i,j)epsilon) (A)\d(ij) - c(ij)\ is minimum. We show that the dual of the inverse spanning tree problem is a bipartite node weighted matching problem on a specially structured graph (which we call the path graph) that contains m nodes and as many as (m - n + 1)(n - 1) = O(nm) arcs. We first transform the bipartite node weighted matching problem into a specially structured minimum cost flow problem and use its special structure to develop an O(n(3)) algorithm. We next use its special structure more effectively and develop an O(n(2)log n) time algorithm. This improves the previous O(n(3)) time algorithm due to Sokkalingam et al. (1999, Oper. Res. 47, 291-298). (C) 2000 Academic Press.