Two new heuristics for the dominating tree problem

摘要

Dominating Tree Problem (DTP) aims to find a dominating tree (d T r e e) of minimum cost on a given connected, undirected and weighted graph in such a way that a vertex in the graph is either in d T r e e or adjacent to a vertex in d T r e e. A solution (d T r e e) to this problem can be used as routing backbone in wireless sensor network. Being a \(\mathcal {NP}\)-Hard problem, several problem-specific heuristics and metaheuristic techniques have been proposed. This paper presents two new heuristics for the DTP. First one is a new problem-specific heuristic that exploits the problem structure effectively, whereas the other is an artificial bee colony (ABC) algorithm. The proposed ABC for the DTP is different from the existing ABC algorithm for the DTP in the literature on its two main components: initial solution generation, and determining a neighboring solution. Computational results show on a set of standard benchmark instances that the proposed problem-specific heuristic and ABC algorithm for the DTP demonstrate the superiority over all existing problem-specific heuristics and metaheuristic techniques respectively in the literature.