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

Xiong, YP

doi:10.1109/TEVC.2004.840145

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

2005-02-01

32

PRE

AI

DOI：10.1109/TEVC.2004.840145

原文链接

原文求助

摘要

En 中文

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.

Keyword:

genetic algorithm (GA)

NP-hard

spanning trees

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

摘要

期刊

机构

引用论文