Hits:

Indexed by:会议论文

Date of Publication:2010-07-07

Included Journals:EI、Scopus

Page Number:217-224

Abstract:The Generalized Minimum Spanning Tree problem (GMST) has attracted much attention during the last few years. Since it is intractable, many heuristic algorithms have been proposed to solve large GMST instances. Motivated by the effectiveness and efficiency of the muscle (the union of all optimal solutions) for solving other NP-hard problems, we investigate how to incorporate the muscle into heuristic design for GMST. Firstly, we demonstrate that it's NP-hard to obtain the muscle for GMST. Then we show that the muscle can be well approximated by the principle and subordinate candidate sets, which can be calculated on a reduced version of GMST. Therefore, a Dynamic cAndidate set based Search Algorithm (DASA) is presented in this paper for GMST. In contrast to existing heuristics, DASA employs those candidate sets to initialize and optimize solutions. During the search process, those candidate sets are dynamically adjusted to include in new features provided by good solutions. Since those candidate sets cover almost all optimal solutions, the search space of DASA can be dramatically reduced so that elite solutions can be easily found in a short time. Extensive experiments demonstrate that our new algorithm slightly outperforms existing heuristic algorithms in terms of solution quality. Copyright 2010 ACM.