# 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: | |

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 |

Repository Staff Only: item control page

Metis ID: 213203