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

Bendali, Fatiha; Mailfert, Jean; Mameri, Djelloul

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

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.

Classification : 05C69, 05C85
Mots clés : Dominating set, maximal independent set, minimum weakly connected independent set, wireless sensor networks, approximation, implicit enumeration

I.F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, Wireless sensor networks: A survey, Comput. Networks 38 (2002) 393–422. | DOI

K.M. Alzoubi, P.J. Wan and O. Frieder, Weakly Connected Dominating Sets and Spanners in Wireless Ad Hoc Networks. Proceedings of the 23rd International Conference on Distributed Computing Systems (2003).

N. Bourgeois, F. Della Croce, B. Escoffier and V.Th. Paschos, Fast algorithms for min independent dominating set, Discrete Appl. Math. 161 (2012) 558–572. | DOI | Zbl

M.S. Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput. 27 (1998) 1671–1694. | DOI | Zbl

Y.P. Chen and A.L. Liestman, Approximating Minimum Size Weakly-Connected Dominating Sets for Clustering Mobile Ad Hoc Networks, The 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (2002).

X. Cheng, X. Cheng, D.Z. Du and M. Cardei, Connected Domination in multihop Ad Hoc Wireless Networks. Proceedings of the 6th International Conference on Computer Science and Informatics (2002).

B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit Disk Graphs. Discrete Math. 86 (1990) 165–177. | DOI | Zbl

D.G. Corneil and Y. Perl, Clustering and domination in perfect graphs. Discrete Appl. Math. 9 (1984) 27–39. | DOI | Zbl

J.E. Dunbar, J.W. Grossman, J.H. Hattingh, S.T. Hedetniemi and A.A. Mcrae. On Weakly connected Domination in graphs, Discrete Math. 167-168 (1997) 261–269. | DOI | Zbl

M. Farber, Independent domination in chordal graphs, Operation Res. Lett. 1 (1982) 134–138. | DOI | Zbl

M. Farber and J. M. Keil, Domination in permutation graphs, J. Algorithms 6 (1985) 309–321. | DOI | Zbl

E. Fleury and D. Simplot-Ryl, Réseaux de capteurs, théorie et modélisation. Lavoisier (2009).

M.R. Garey and D.S. Johnson,Computers and intractability: A guide to the theory of NP-completeness. Freeman, New York (1979). | Zbl

S. Gaspers and M. Liedloff, A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, Fomin, Lect. Notes Comput. Sci. 4271 (2006) 78–89. | DOI | Zbl

A.M. Geoffrion, Integer programming by implicit enumeration and Balas’ Method, Siam Review 9 (1967) 178–190. | DOI | Zbl

S. Guha and S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica 20 (1998) 374–387. | DOI | Zbl

M.M. Halldórsson, Approximating the minimum maximal independence number, Information Processing Lett. 46 (1993) 169–172. | DOI | Zbl

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in graphs: Advanced Topics, Marcel Dekker, Inc. (1998). | Zbl

R.W. Irving, On approximating the minimum independent dominating set, Information Processing Lett. 37 (1991) 197–200. | DOI | Zbl

B. Jeremy, D. Min, T. Andrew and C. Xiuzhen, Connected Dominating set in Sensor networks and manets, Handbook of Combinatorial optimization. Springer. (2004). | Zbl

D.S. Johnson, C.H. Papadimitriou and M. Yannakakis. On generating all maximal independent sets, Inform. Processing Lett. 27 (1988) 119–123. | DOI | Zbl

C. Laforest and R. Phan, Experimentations on an exact algorithm for the minimum independent dominating set problem in graphs using clique partition. RAIRO 47 (2013) 199–221. | DOI | Numdam | Zbl

Y.S. Li, M.T. Thai, F. Wang, C.W. Yi, P.J. Wan and D.Z. Du, On Greedy Construction of Connected Dominating Sets in Wireless Networks, J. Wireless Communications and Mobile Computing 5 (2005) 927–932. | DOI

C. Liu and Y. Song, Exact algorithms for finding the minimum independent dominating set in graphs. ISAAC, Lect. Notes Comput. Sci. 4288 (2006) 439–448. | DOI | Zbl

J.M. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23–28. | DOI | Zbl

A. Potluri and A. Negi, Some observations on algorithms for computing minimum independent dominating set, IC3, Communications in Computer and Information Science, 168 (2011) 57–68. | DOI

G. Reinelt, TSPLIB-A Traveling Salesman Problem Library, Informs J. Comput. 3 (1991) 376–384. | DOI | Zbl

A.C. Santos, F. Bendali, J. Mailfert, C. Duhamel and K.M. Hou, Heuristics for designing Energy-efficient Wireless Sensor Network Topologies. J. Networks 4 (2009) 436–444. | DOI

I. Stojmenovic, M. Seddigh and J. Zunic, Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks, IEEE Transactions on parallel and distributed systems 13 (2002) 14–25. | DOI

P.J. Wan, K.M. Alzoubi and O. Frieder, Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications 9 (2004) 141–149. | DOI

P.J. Wan, L. Wang and F. Yao, Two-Phased Approximation Algorithms for Minimum CDS in Wireless Ad Hoc Networks, IEEE ICDCS (2008) 337–344.

W. Wu, H. Du, X. Jia, Y. Li and S.C.H. Huang, Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theoret. Comput. Sci. 352 (2006) 1–7. | DOI | Zbl