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

Brüggemann, Tobias and Monnot, Jérôme and Woeginger, Gerhard J. (2003) Local search for the minimum label spanning tree problem with bounded color classes. Operations Research Letters (3). pp. 195-201. ISSN 0167-6377

PDF
Restricted to UT campus only: Request a copy
220Kb

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 r3. 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 k3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.
Item Type:	Article
Copyright:	© 2003 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/75016
Official URL:	http://dx.doi.org/10.1016/S0167-6377(02)00241-9
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 213203