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é.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Graphs, flows, combinatorial algorithms and approximation |
| Keywords | : | Clique maximum ; Poupées Russes ; Branch and Bound |
| PDF version | : |  PDF version |
