Local search for the minimum label spanning tree problem with bounded color classes

Local search for the minimum label spanning tree problem with bounded color classes

0.00 Avg rating0 Votes
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: , ,
Keywords: minimum spanning tree, graph colouring
Abstract:

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 r times in the input graph. This special case is polynomially solvable for r=2, and NP- and APX-complete for any fixed r≥3. We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k=2 any local optimum yields an (r+1)/2-approximation of the global optimum, and that this bound is tight. For every k≥3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.

Reviews

Required fields are marked *. Your email address will not be published.