Design Of Exact Algorithms And Heuristics For The Tree Cover Problem

Tree cover problem is a basic combinatorial optimization problem,which is of great research value in many applications,such as the planning of telephone machine room,network machine room and power plant.There are four types of the tree cover problems,including the Min-Max Tree Cover problem,the rooted Min-Max Tree Cover problem,the Bounded Tree Cover problem and the rooted Bounded Tree Cover problem.The study of the tree cover problem not only has important meaning in applications,but also has important research value for other similar problems,such as the cycle cover problem,vehicle routing problem,path cover problem and set cover problem.This paper,studies the Min-Max Tree Cover problem and the Bounded Tree Cover problem.Given a graph and a positive integers k,the Min-Max Tree Cover problem requires that all vertices in the graph be covered with at most k trees,and the cost of the tree with the highest cost is minimized.Given a graph and a bound B,the Bounded Tree Cover problem requires that as few trees as possible cover all vertices on the graph,and the cost of each tree in the solution should not exceed B.At present,the research work on these two problems mainly focuses on the approximation algorithms,among which,the best approximation ratio of the Min-Max Tree Cover problem is 3,and the best approximation ratio of the bounded tree cover problem is 2.5.As for the exact algorithm,no known results have been seen in literature.In this paper,the exact algorithms and heuristics for the Min-Max Tree Cover problem and the Bounded Tree Cover problem are studied.the time complexity of the exact algorithm for the Min-Max Tree Cover problem is proved to be O*(3n).This is the first nontrivial exact algorithm for the Min-Max Tree Cover problem.Using a similar method,we design the first nontrivial exact algorithm for the Bounded Tree Cover problem,and prove that the time complexity of the algorithm is O*(3n).In addition,by using the inclusion-exclusion principle and dynamic programming techniques,we also obtain an intermediate solution for the Bounded Tree Cover problem,which is obtained time complexity O*(2n).The generation of intermediate solutions may provide inspirations for other exact algorithms and heuristics.In addition,this paper also studies the heuristics for the Min-Max Tree Cover problem,and designs six heuristics for the Min-Max Tree Cover problem,among which four are based on the minimum spanning tree and the other two are greedy algorithms based on global segmentation.Finally,a great deal of test sample are designed for it.By changing the values of parameters,it is found that in different scenarios,different heuristics have different utility and different solutions are obtained.Experimental results show that the heuristic based on the global segmentation and multiple average behaves the best.This heuristic performs well for general values of the number of vertices,the edge weight and the segmentation number.only when the number of vertices n and segmentation number k particularly are large,the algorithm will cost more time.