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
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;
Journal_Title :
Evolutionary Computation, IEEE Transactions on
DOI :
10.1109/TEVC.2004.840145
