DocumentCode
1239073
Title
A one-parameter genetic algorithm for the minimum labeling spanning tree problem
Author
Xiong, Yupei ; Golden, Bruce ; Wasil, Edward
Author_Institution
Dept. of Math., Univ. of Maryland, College Park, MD, USA
Volume
9
Issue
1
fYear
2005
Firstpage
55
Lastpage
60
Abstract
Given a connected, undirected graph G whose edges are labeled (or colored), the minimum labeling spanning tree (MLST) problem seeks a spanning tree on G with the minimum number of distinct labels (or colors). In recent work, the MLST problem has been shown to be NP-hard and an effective heuristic [maximum vertex covering algorithm (MVCA)] has been proposed and analyzed. We use a one-parameter genetic algorithm (GA) to solve the problem. In computational tests, the GA clearly outperforms MVCA.
Keywords
computational complexity; genetic algorithms; trees (mathematics); NP hard problem; maximum vertex covering algorithm; minimum labeling spanning tree problem; one parameter genetic algorithm; undirected graph; Algorithm design and analysis; Communication networks; Frequency; Genetic algorithms; Labeling; Mathematics; Polynomials; Testing; Tree graphs;
fLanguage
English
Journal_Title
Evolutionary Computation, IEEE Transactions on
Publisher
ieee
ISSN
1089-778X
Type
jour
DOI
10.1109/TEVC.2004.840145
Filename
1395851
Link To Document