Soit G=(V,E) un graphe non orienté connexe. Un sous-ensemble W de V est
un indépendant faiblement connexe de G (Weakly Connected Independent Set ou wcis)
si $W$ est un stable de $G$ et si le graphe partiel G_{W}=(V,[W,V\backslash W]) est connexe.
Cette structure a été utilisée par [alzoubi2002] pour déterminer un ensemble dominant faiblement connexe
et par [santos2009] en tant que topologie dans les réseaux de capteurs sans fil.
Dans cette communication, nous décrivons une formulation en nombres entiers
de l'enveloppe convexe des vecteurs caractéristiques des indépendants
faiblement connexes. Nous proposons aussi des inégalités valides qui visent
à renforcer la relaxation réelle. Des opérations simples sur les graphes nous permettront
d'obtenir le polytope des indépendants faiblement connexes dans des classes particulières
de graphes. Enfin, nous présentons les premiers tests numériques d'un algorithme de branchements
et de coupes.
[alzoubi2002] K. M. Alzoubi and P-J. Wan and O. Frieder, Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks,ACM Mobihoc, 2002.
[santos2009] A. C. Santos and F. Bendali and J. Mailfert and C. Duhamel and K. M. Hou, Heuristices for designing Energy-efficient Wireless Sensor Network Topologies,
Journal of networks, 4(6): 436-444, 2009,
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Polyhedral approaches, extended formulations and decomposition in integer programming |
| Keywords | : | Graphe ; indépendant faiblement connexe ; formulation en nombres entiers ; algorithme de branchements et de coupes |
| PDF version | : |  PDF version |
