Weighted Steiner Connected Dominating Set and Its Application to Multicast Routing in Wireless MANETs

In this paper, the authors first propose three centralized learning automata-based heuristic algorithms for approximating a near optimal solution to the minimum Weight Steiner Connected Dominating Set (WSCDS) problem. Finding the Steiner connected dominating set of the network graph is a promising approach for multicast routing in wireless ad-hoc networks. Therefore, they present a distributed implementation of the last approximation algorithm proposed in this paper (Algorithm III) for multicast routing in wireless mobile ad-hoc networks. The proposed WSCDS algorithms are compared with the well-known existing algorithms and the obtained results show that Algorithm III outperforms the others both in terms of the dominating set size and running time.