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

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

Original

Original request for help

Save

Abstract

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.

Keywords:

genetic algorithm (GA)

NP-hard

spanning trees

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

Abstract

Journal

Organization

Cited Papers