Neighborhood Search for the Bounded Diameter Minimum Spaning Tree
Many optimization problems including the network design problem of finding the bounded diameter minimum spanning tree are computationally intractable. Therefore, a practical approach for solving such problems is to employ heuristic algorithms that can find solution close to the optimal one within a reasonable amount of time. Neighborhood search algorithms are a wide class of algorithms where at each iteration an improved solution is found by searching the "Neighborhood" of the current solution. A critical issue in the design of a neighborhood search algorithm is the choice of the neighborhood structure. Literature reveals that the larger the neighborhood, the better is the quality of the locally optimal solutions and the greater is the accuracy of the final solution obtained.