|
A faster algorithm for the inverse spanning tree problem R.K. Ahuja, and J.B. Orlin, Journal of Algorithms 34, 177-193, 2000 In this paper, we consider the inverse spanning tree problem. Given an undirected graph G0 = (N0, A0) with n nodes, m arcs, an arc cost vector c, and a spanning tree T0, the inverse spanning tree problem is to perturb the arc cost vector c to a vector d so that T0 is a minimum spanning tree with respect to the cost vector d and the cost of perturbation given by |d – c| = å (i,j)Î A |dij – cij| 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(n3) algorithm. We next use its special structure more effectively and develop an O(n2 log n) time algorithm. This improves the previous O(n3) time algorithm due to Sokkalingam, Ahuja and Orlin [1999]. |