A Node-Centric Artificial Bee Colony Framework for Dominating Tree Construction

Abstract

Designing efficient communication backbones is crucial for modern network applications, such as wireless sensor networks & multicast routing, and the dominating tree problem (DTP) was formulated by keeping these applications in mind. The DTP is an NP-hard problem that involves constructing a tree in a connected, edge-weighted, undirected graph with the aim of minimizing the total edge cost while ensuring that every vertex is either part of the tree or adjacent to a vertex in the tree. This paper presents a node-based artificial bee colony (ABC) framework for the DTP, which incorporates problem-specific variation operators designed to effectively navigate the solution space. Unlike most previous approaches for DTP, which focus on selecting edges, the proposed ABC framework first selects the nodes and then constructs the minimum spanning tree over the subgraph induced by selected nodes and a few additional nodes lying on the shortest paths joining pairs of selected nodes. The proposed ABC framework is tested on standard benchmark instances and results are compared with those of the best performing methods in the literature. Experimental results show the effectiveness of the proposed framework. The proposed ABC framework obtained solutions as good as or better than the best performing methods on a large majority of instances. The proposed algorithm also enhanced the best known results for three benchmark instances.