Un compromis temps-espace pour la résolution de réseaux de contraintes par décomposition
Résumé
Nous revenons ici sur une méthode de résolution de CSP par décomposition introduite dans [16] et qui est appelée Regroupement Cyclique. Alors que [16] se limitait à présenter uniquement les principes de la méthode, dans cette contribution, nous montrons comment celle-ci peut être rendue opérationnelle, notamment par une exploitation idoine des propriétés des sous-graphes triangulés. Dans un second temps, nous présentons des résultats formels qui démontrent que le Regroupement Cyclique réalise effectivement un compromis temps-espace en termes de complexités théoriques. Nous concluons cet article en présentant quelques résultats expérimentaux qui montrent que le Regroupement Cyclique peut être efficace en pratique.