Title :
New Recombination Operator in Genetic Algorithm For Solving the Bounded Diameter Minimum Spanning Tree Problem
Author :
Nghia, Nguyen Duc ; Binh, Huynh Thi Thanh
Author_Institution :
Fac. of Inf. Technol., Hanoi Univ. of Technol., Hanoi
Abstract :
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 les D les |V|i - 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.
Keywords :
computational complexity; genetic algorithms; greedy algorithms; mathematical operators; randomised algorithms; trees (mathematics); NP-hard problem; bounded diameter minimum spanning tree problem; connected graph; genetic algorithm; randomized greedy heuristic algorithm; recombination operator; undirected graph; weighted graph; Algorithm design and analysis; Communication networks; Costs; Design optimization; Genetic algorithms; Heuristic algorithms; Information technology; Joining processes; Tree graphs; Upper bound; bounded diameter minimum spanning tree; genetic algorithm; greedy heuristic;
Conference_Titel :
Research, Innovation and Vision for the Future, 2007 IEEE International Conference on
Conference_Location :
Hanoi
Print_ISBN :
1-4244-0694-3
DOI :
10.1109/RIVF.2007.369143
