New Recombination Operator in Genetic Algorithm For Solving the Bounded Diameter Minimum Spanning Tree Problem

摘要

Given a connected, weighted, undirected graph G=(V, E) and a bound D, Bounded Diameter Minimum Spanning Tree problem (BDMST) seeks spanning tree on G with smallest weight in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 < D < |V| -1. In present paper a new randomized greedy heuristic algorithm and a new recombination method in genetic algorithm for solving BDMST are developed. Results of computational experiments are reported to show the efficiency of these algorithms.