Algorithm Research For The Constrained Minimum Spanning Tree Problem

The problem of identifying minimum spanning tree(MST) of a connected, undirected graph is a classical network optimization problem which can be solved efficiently in polynomial time by Kruskal algorithm and Prim algorithm. Unfortunately, practical problems often need some constraints on the spanning tree. Two typical representatives of these related problems are the degree-constrained minimum spanning tree problem and the bounded-diameter minimum spanning tree problem. They have wide applications in the real world, such as communication networks, circuit design, pipeline laying and so on. So, it's of practical significance for us to study the solution algorithms.The main work is summarized as follows:Firstly, a new fast algorithm is proposed for the degree-constrained minimum spanning tree problem. The new fast algorithm consists of two major parts. The first part describes how to construct a degree-constrained tree. The second part presents an improvement strategy based on the degree-constrained tree obtained from the first part. By the improvement strategy, we can obtain a better solution. The complexity of the algorithm is analyzed and the validity theorem is proved. Many numerical tests show that the new fast algorithm has very good performance.Secondly, a genetic algorithm for the bounded-diameter minimum spanning tree problem is designed based on a permutation coding scheme. The algorithm adopts a new mutation operator and a local search scheme. The new mutation operator improves the diversity of the population effectively, and the local search scheme based on the permutation coding scheme can obtain an individual with a better fitness. At the same time, the validity of the local search scheme is proved. A large number of experiments show that the genetic algorithm is very effective.