A Faster Algorithm for the Inverse Spanning Tree Problem

✍ Scribed by Ravindra K. Ahuja; James B. Orlin

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 149 KB
• Volume: 34
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1052

✦ Synopsis

In this paper, we consider the inverse spanning tree problem. Given an undi-0 Ž 0 0 . rected graph G s N , A with n nodes, m arcs, an arc cost vector c, and a spanning tree T 0 , the inverse spanning tree problem is to perturb the arc 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 y c s Ý

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 y n q 1 n y 1 Ž . s 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 Ž 3 . to develop an O n algorithm. We next use its special structure more effectively Ž 2 . Ž 3 . and develop an O n log n time algorithm. This improves the previous O n time Ž . algorithm due to Sokkalingam et al. 1999, Oper. Res. 47, 291᎐298 . ᮊ 2000 Academic Press 1. INTRODUCTION In this paper, we study the inverse spanning tree problem. Inverse optimization is a relatively new area of research within the operations research community. Some references on inverse optimization include the 177