Algorithms on partial inverse min–max spanning tree problem under the l∞-norm

Abstract

Given a connected edge-weighted graph G and a forest F of G , the goal of the partial inverse min–max spanning tree problem is to change the weight function as little as possible, so that there is a min–max spanning tree with respect to the new weight function containing F . In this paper, we study this problem under the l ∞ -norm. By studying the characteristics of a special class of optimal solution and the optimal value, combining the algorithm for the decision version of this problem with the binary search method, we provide a polynomial time algorithm with time complexity O ( n m log n m ) to solve this problem. In addition, for a special case, partial inverse min–max spanning tree problem without the capacity constraint under the unit l ∞ -norm, we show that it can be solved in linear time.