  This paper studies constructive heuristics for the minimum labelling spanning
tree (MLST) problem. The purpose is to find a spanning tree that uses edges
that are as similar as possible. Given an undirected labeled connected graph
(i.e., with a label or color for each edge), the minimum labeling spanning tree
problem seeks a spanning tree whose edges have the smallest possible number of
distinct labels. The model can represent many real-world problems in
telecommunication networks, electric networks, and multimodal transportation
networks, among others, and the problem has been shown to be NP-complete even
for complete graphs. A primary heuristic, named the maximum vertex covering
algorithm has been proposed. Several versions of this constructive heuristic
have been proposed to improve its efficiency. Here we describe the problem,
review the literature and compare some variants of this algorithm.
