Learning AutomataBased Algorithms for Finding Minimum Weakly Connected Dominating Set in Stochastic Graphs

A Weakly Connected Dominating Set (WCDS) of graph G is a subset of G so that the vertex set of the given subset and all vertices with at least one endpoint in the subset induce a connected sub-graph of G. Finding the WCDS is a new promising approach for clustering the wireless networks. The Minimum WCDS (MWCDS) problem is known to be NP-hard, and several approximation algorithms have been proposed for solving MWCDS in deterministic graphs. However, to the best of the authors' knowledge no work has been done on finding the WCDS in stochastic graphs.