New Multi-parent Recombination in Genetic Algorithm for Solving Bounded Diameter Minimum Spanning Tree Problem

Author

Binh, Huynh Thi Thanh ; Nghia, Nguyen Duc

Author_Institution

Ha Noi Univ. of Technol., Ha Noi, Vietnam

fYear

2009

fDate

1-3 April 2009

Firstpage

283

Lastpage

288

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| - 1. This paper proposes three new multi-parent recombination operators using different methods to choose parents in genetic algorithm for solving bounded diameter minimum spanning tree problem. Results of computational experiments are reported to show the efficiency of proposed algorithms.

Keywords

computational complexity; genetic algorithms; optimisation; trees (mathematics); NP-hard problem; bounded diameter minimum spanning tree problem; connected graph; genetic algorithm; multi-parent recombination; undirected graph; weighted graph; Algorithm design and analysis; Communication networks; Cost function; Database systems; Deductive databases; Design optimization; Genetic algorithms; Polynomials; Quality of service; Tree graphs; bounded diameter minimum spanning tree; genetic algorithm; multi-parent;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Information and Database Systems, 2009. ACIIDS 2009. First Asian Conference on

Conference_Location

Dong Hoi

Print_ISBN

978-0-7695-3580-7

Type

conf

DOI

10.1109/ACIIDS.2009.89

Filename

5176007