On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm

Laboratoire LIMOS – UMR 6158 CNRS, Campus des Cézeaux, 63173 Aubière Cedex, France.
bendali@isima.fr

Received: 18 September 2013
Accepted: 1 August 2014

Abstract

Modeling topologies in Wireless Sensor Networks principally uses domination theory in graphs. Indeed, many dominating structures have been proposed as virtual backbones for wireless networks. In this paper, we study a dominating set that we call Weakly Connected Independent Set (wcis). Given an undirected connected graph G = (V,E), we say that an independent set S in G is weakly connected if the spanning subgraph (V, [ S,V \ S ]) is connected, where [ S,V \ S ] is the set of edges having exactly one end in S. The minimum weakly independent connected set problem consists in determining a wcis of minimum size in G. First, we discuss some complexity and approximation results for that problem. Then we propose an implicit enumeration algorithm which computes a minimum wcis in a graph with n vertices with a running time O^∗(1.4655ⁿ) and polynomial space. Processing results are given that show that our enumeration program solves the mwcis problem for graphs whose number of vertices is less than 120.