Article ID: | iaor2004361 |
Country: | Netherlands |
Volume: | 31 |
Issue: | 3 |
Start Page Number: | 195 |
End Page Number: | 201 |
Publication Date: | May 2003 |
Journal: | Operations Research Letters |
Authors: | Woeginger Gerhard J., Monnot Jrme, Brggemann Tobias |
Keywords: | minimum spanning tree, graph colouring |
In the Minimum Label Spanning tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most