Thursday 27
Graphs, flows, combinatorial algorithms and approximation
Vincent Chau
› 12:00 - 12:30 (30min)
› Bât B - TD 43
Application de la méthode des Poupées Russes pour une résolution efficace du problème de la clique maximum
Ricardo Correa  1@  , Bertrand Lecun  2@  , Thierry Mautor  2@  , Philippe Michelon  3@  
1 : Universidade Federal do Ceara - Bresil
2 : Parallélisme, Réseaux, Systèmes d'information, Modélisation  (PRISM)  -  Website
CNRS : UMR8144, Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)
45 avenue des Etats-Unis Bâtiment Descartes 78035 Versailles CEDEX -  France
3 : Laboratoire Informatique d'Avignon  (LIA)  -  Website
Centre d'Enseignement et de Recherche en Informatique - CERI, Université d'Avignon et des Pays de Vaucluse
339 Chemin des Meinajaries Agroparc BP 1228 84911 Avignon cedex 9 -  France

La méthode des Poupées Russes (Russian Dolls algorithm) a été proposée en 1996 par Verfaillie et al. Peu utilisée depuis lors, à l'exception de quelques travaux pour la résolution de problèmes d'optimisation discrète par Ostergard et
Vaskelainen, cette méthode consiste à résoudre itérativement des sous-problèmes de plus en plus gros (poupées encastrées) jusqu'à la résolution du problème global en utilisant autant que possible les résultats obtenus lors de la résolution
des sous-problèmes précédents (poupées plus petites).

Cette méthode peut être utilisée très efficacement pour le problème très classique de recherche de la clique maximum - de plus grande cardinalité - (ou du stable maximum). Chaque poupée (sous-problème) est résolue par une méthode Branch and Bound où la borne est fournie par une procédure de coloration des sommets. La connaissance accumulée par les poupées plus petites permet de réduire sensiblement la taille des arborescences de recherche. De plus, l'implémentation implique de nombreuses opérations ensemblistes qui utilisent efficacement les instructions parallèles des processeurs modernes (bit-parallélisme).

Ainsi, les résultats obtenus se montrent extrèmement concurrentiels égalant et même surpassant sur certaines instances classiques de la littérature (Dimacs instances) les meilleurs résultats existants sur ce problème très classique et très
traité.



Online user: 1