Research Of Bounded-Diameter Minimum Spanningtree Problem Based On Genetic Algorithm

Minimum spanning tree is a classic combinatorial optimization problem. Due to the transmission speed and signal quality and ease of maintenance and so on, the diameter of the minimum spanning tree is needed to be limited in the actual application. So there are the problems of bounded-diameter minimum spanning tree (BDMST).Namely given an undirected, weighted graph and a positive integer D, to seek the bounded-diameter minimum spanning tree of the graph with smallest weight, among all spanning tree of the graph, which contain no path with more than D edges. In general, the BDMST is a NP Hard problem when the diameter is limited in [4, n-1). We mostly adopts the heuristic algorithm or genetic algorithm or other modern optimization method for large scale BDMST, which is based on assumption of completely connected graph. In this paper we proposed a new genetic algorithm to solve BDMST for the noncomplete graph. Promising experimental results demonstrate the effectiveness of the proposed method.