A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Heuristics for the central tree problem
Tekijät: Bang-Jensen Jorgen, Nikulin Yuri
Kustantaja: SPRINGER
Julkaisuvuosi: 2010
Journal: Journal of Heuristics
Tietokannassa oleva lehden nimi: JOURNAL OF HEURISTICS
Lehden akronyymi: J HEURISTICS
Numero sarjassa: 5
Vuosikerta: 16
Numero: 5
Aloitussivu: 633
Lopetussivu: 651
Sivujen määrä: 19
ISSN: 1381-1231
DOI: https://doi.org/10.1007/s10732-009-9111-9
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.