Wednesday 26
Polyhedral approaches, extended formulations and decomposition in integer programming
Pierre Fouilhoux
› 14:00 - 14:20 (20min)
› Bât. A - TD 33
Approche polyèdrale pour le problème de l'indépendant faiblement connexe de cardinalité minimum
Djelloul Mameri  1@  , Fatiha Bendali  1, *@  , Jean Mailfert  1, *@  
1 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
Institut Français de Mécanique Avancée, Université Blaise Pascal - Clermont-Ferrand II, Université d'Auvergne - Clermont-Ferrand I, CNRS : UMR6158
Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex -  France
* : Corresponding author

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,


Online user: 2