New heuristic approaches for the dominating tree problem

Given an undirected, connected and edge-weighted graph, the dominating tree problem (DTP) seeks on this graph a tree with minimum total edge weight such that each vertex of the graph is either in this tree or adjacent to a vertex in this tree. The DTP is a NPNP-Hard problem. In the literature only two heuristics for this problem are proposed so far in spite of the fact that it has several practical applications in the field of wireless sensor networks. In this paper, we propose one heuristic and two swarm intelligence techniques, viz. an artificial bee colony algorithm and an ant colony optimization algorithm for the DTP. Computational results show the effectiveness of our approaches.

Figure optionsDownload as PowerPoint slideHighlights
• In this paper, we have proposed three heuristic approaches viz. H_DT, ABC_DT and ACO_DT for the dominating tree problem (DTP).
• H_DT is a problem-specific heuristic and produces much better results in comparison with other problem-specific heuristics for the DTP.
• ABC_DT and ACO_DT are respectively based on artificial bee colony algorithm and ant colony optimization algorithm.
• Performance of ABC_DT and ACO_DT are comparable in terms of solution quality.
• Though, ACO_DT produces slightly better results, it is slower than ABC_DT on large instances.