The minimum labeling spanning trees

One of the fundamental problems in graph theory is to compute a minimum weight spanning tree. In this paper, a variant of spanning trees, called the minimum labeling spanning tree, is studied. The purpose is to find a spanning tree that tries to use edges that are as similar as possible. Giving each edge a label, the minimum labeling spanning tree is to find a spanning tree whose edge set consists of the smallest possible number of labels. This problem is shown to be NP-complete even for complete graphs. Two heuristic algorithms and an exact algorithm, based on the A*-algorithm, are presented. According to the experimental results, one of the heuristic algorithms is very effective and the exact algorithm is very efficient. (C) 1997 Elsevier Science B.V.