An efficient algorithm for generalized minimum spanning tree problem

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