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

T. Brueggemann, Jérôme Monnot, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

48 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)195-201
Number of pages7
JournalOperations research letters
Volume31
Issue number3
DOIs
Publication statusPublished - 2003

Keywords

  • IR-75016
  • Approximation algorithms
  • Local search
  • Complexity
  • Combinatorial optimization
  • METIS-213203
  • APX-completeness
  • Graph algorithms

Fingerprint Dive into the research topics of 'Local search for the minimum label spanning tree problem with bounded color classes'. Together they form a unique fingerprint.

Cite this