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

Bendali, Fatiha¹ ; Mailfert, Jean¹  ; Mameri, Djelloul¹ 

¹ Laboratoire LIMOS – UMR 6158 CNRS, Campus des Cézeaux, 63173 Aubière Cedex, France.

RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 313-334

Résumé

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\setminus S\left]\right)$ is connected, where $[S,V\setminus 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}^n)$ 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.

Détail

DOI : 10.1051/ro/2014040

Classification : 05C69, 05C85
Keywords: Dominating set, maximal independent set, minimum weakly connected independent set, wireless sensor networks, approximation, implicit enumeration