Heuristics for the central tree problem |
| |
Authors: | Jørgen Bang-Jensen Yury Nikulin |
| |
Institution: | 1.Department of Mathematics and Computer Science,University of Southern Denmark,Odense,Denmark;2.Department of Mathematics,University of Turku,Turku,Finland |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|