• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Heuristics for the central tree problem

Joergen Bang-Jensen, Yury Nikulin, Heuristics for the central tree problem . Journal of Heuristics 16(5), 633–651, 2010.

Abstract:

This paper addresses the central spanning tree problem (CTP). The problem consists in finding a spanning tree that minimizes the so-called robust deviation, i.e. deviation from a maximally distant tree. The distance between two trees is measured by means of the symmetric difference of their edge sets. The central tree problem is known to be NP-hard. We attack the problem with a hybrid heuristic consisting of: (1) a greedy construction heuristic to get a good initial solution and (2) fast local search improvement. We illustrate computationally efficiency of the proposed approach

BibTeX entry:

@ARTICLE{jBaNi10a,
  title = {Heuristics for the central tree problem },
  author = {Bang-Jensen, Joergen and Nikulin, Yury},
  journal = {Journal of Heuristics},
  volume = {16},
  number = {5},
  publisher = {Springer},
  pages = {633–651},
  year = {2010},
}

Belongs to TUCS Research Unit(s): Turku Optimization Group (TOpGroup)

Publication Forum rating of this publication: level 2

Edit publication