A one-parameter genetic algorithm for the minimum labeling spanning tree problem

被引：31

作者：

Xiong, YP ^{[1
]}

Golden, B

Wasil, E

机构：

[1] Univ Maryland, Dept Math, College Pk, MD 20742 USA

[2] Univ Maryland, RH Smith Sch Business, College Pk, MD 20742 USA

[3] American Univ, Kogod Sch Business, Washington, DC 20016 USA

来源：

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION | 2005年 / 9卷 / 01期

关键词：

genetic algorithm (GA); NP-hard; spanning trees;

D O I：

10.1109/TEVC.2004.840145

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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. In this paper, we use a one-parameter genetic algorithm (GA) to solve the problem. In computational tests, the GA clearly outperforms MVCA.

引用

页码：55 / 60

页数：6

共 8 条

[1] Local search for the minimum label spanning tree problem with bounded color classes [J].