Search

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

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. We use a one-parameter genetic algorithm (GA) to solve the problem. In computational tests, the GA clearly outperforms MVCA.

Given a connected, undirected graph G whose edges are labeled (or colored), the colorful traveling salesman problem (CTSP) seeks a Hamiltonian tour of G with the minimum number of distinct labels (or colors). We prove that the CTSP is NP-complete and we present a heuristic algorithm and a genetic algorithm to solve the problem.