Volume 49, Number 2, April-May 2015New challenges in scheduling theory
|Page(s)||313 - 334|
|Published online||18 December 2014|
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,
Accepted: 1 August 2014
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.4655n) 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.
Mathematics Subject Classification: 05C69 / 05C85
Key words: Dominating set / maximal independent set / minimum weakly connected independent set / wireless sensor networks / approximation / implicit enumeration
© EDP Sciences, ROADEF, SMAI 2014
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.