A two-level meta-heuristic approach for the minimum dominating tree problem

摘要

1 Introduction The minimum dominating tree(MDT)problem was first proposed by Zhang et al.[1]to produce a routing backbone of a WSN.Shin et al.[2]proved that the MDT problem is NP-hard and introduced an approximation framework for solving it.Recent important MDT problem algorithms are the artificial bee colony(ABC_DT)algorithm and ant colony optimization(ACO_DT)algorithm proposed by Sundar and Singh[3],the evolutionary algorithm with guided mutation(EA/G-MP)proposed by Chaurasia and Singh[4],the variable neighborhood search algorithm proposed by Dražićet al.[5],one improved artificial bee colony(ABC_DTP)algorithm proposed by Singh and Sundar[6],and a hybrid algorithm combining genetic algorithm proposed by Hu et al.[7].In this paper,we develop a two-level meta-heuristic(TLMH)for solving the MDT problem,aiming to find a dominating tree with the minimum weight for a given graph.