A faster algorithm for the inverse spanning tree problem

In this paper, we consider the inverse spanning tree problem. Given an undi rected 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 t he are cost vector c to a vector d so that T-0 is a minimum spanning tree w ith 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 d ual of the inverse spanning tree problem is a bipartite node weighted match ing 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 fi rst transform the bipartite node weighted matching problem into a specially structured minimum cost flow problem and use its special structure to deve lop an O(n(3)) algorithm. We next use its special structure more effectivel y 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-29 8). (C) 2000 Academic Press.