The Partial Inverse Least Uniform Spanning Tree Problem under Weighted l1 Norm

摘要

In this paper, we consider the partial inverse least uniform spanning tree problem under weighted l1 norm, which is how to adjust the parameters with the minimum cost in a simple undirected weighted graph so that a partially given forest becomes a part of the new least uniform spanning tree. We shall show that this problem can be solved by strongly polynomial algorithm.