The Study On Partial Inverse Min-max Spanning Tree Problem Under Some Bottleneck Type Norms

Min-max spanning tree problem is a classical problem in combinatorial optimiza-tion.Its purpose is to find a spanning tree that minimizeits its maximum edge weight in a given edge weighted graph.Given a connected graph G,an edge weight vector w and a forest F of G,the partial inverse min-max spanning tree problem(PIMMST)is to find a new weight vector w*,satisfying there exists a min-max spanning tree T of G with respect to w*such that F(?)E(T)and the gap between w and w*is minimized.In this thesis,we study PIMMST under two bottleneck type norms:the weighted bottleneck Hamming distance and the l_∞-norm,respectively.Under the weighted bottleneck Hamming distance,we first study PIMMST with value of optimal tree restriction,and show that this problem can be solved in strongly polynomial time.Then,by giving the candidate set of value of the optimal trees in poly-nomial scale,we design an algorithm for PIMMST with time complexity O(m~2log m),where m is the number of edges.Meanwhile,we extend above algorithm to solve corre-sponding problems with capacitated constraint.Then,by giving a simpler necessary and sufficient condition for determining the feasible solution of the partial inverse min-max spanning tree problem,we design a faster algorithm with time complexity O(m log m).Furthermore,we also prove that the algorithm can be generalized to solve the problem with capacitated constraint.Under the l_∞-norm,the thesis first considers a special case-partial inverse min-max spanning tree problem under the Unit l_∞-norm,and a linear time algorithm for solving the problem is presented by discovering the characteristics of optimal value and optimal solution of the problem.Further,this thesis studies the decision versions of capacitated partial inverse min-max spanning tree problem under the Unit l_∞-norm and partial inverse min-max spanning tree problem under the l_∞-norm,respectively,and obtains the necessary and sufficient conditions for solving these two decision versions.