Abstract: Established infrastructure makes a great impact on demand changes in particular physical network. It is necessary to adjust the capacities of arcs to improve the service of the network when demand increases. The process of adjusting and optimizing should possible to minimize influences on people's daily life, by considering not only the expansion cost but also the total edges adjustment. In this paper, a network G, the initial capacity of edge e_i and the cost for increasing per unit capacity of e_i are initially set. Two factors: the improvement cost and the total edges adjustment are considered in this problem. The task is to determine new capacities x_i so that the capacity of the network can be increased to the maximum extent, i.e. max{ min_ei∈T x_i,T is the spanning tree of network G }. Firstly two related models are solved instead of the original model. The relations and differences between the two related models and the original problem are analyzed. Then an algorithm is present to solve the original problem in polynomial time. Finally, an example is computed to illustrate the steps of the algorithm and analyze the impacts of parameters to the capacity of the system.

Key words: bottleneck capacity expansion, minimum spanning tree, polynomial time algorithm