.png){kind=icon}
.png){kind=icon}
Return
Improved heuristics for the minimum label spanning tree problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TEVC.2006.877147.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a connected, undirected graph G whose edges are labeled, the minimum label (or labeling) spanning tree (MLST) problem seeks a spanning tree on G with the minimum number of distinct labels. Maximum vertex covering algorithm (MVCA) is a well-known heuristic for the MLST problem. It is very fast and performs reasonably well. Recently, we developed a genetic algorithm (GA) for the MLST problem. The GA and MVCA are similarly fast but the GA outperforms the MVCA. In this paper, we present four modified versions of MVCA, as well as a modified GA. These modified procedures generate better results, but are more expensive computationally. The modified GA is the best performer with respect to both accuracy and running time.
Keywords:
genetic algorithm (GA)
NP-hard
spanning tree
Journal
IF:
12
Papers:
1.8K
Citations:
2.4W
Organization
No organization information available