Un compromis temps-espace pour la résolution de réseaux de contraintes par décomposition - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

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.
Fichier principal
Vignette du fichier
40.pdf (296.02 Ko) Télécharger le fichier

Dates et versions

inria-00000073 , version 1 (26-05-2005)

Identifiants

  • HAL Id : inria-00000073 , version 1

Citer

Philippe Jégou, Cyril Terrioux. Un compromis temps-espace pour la résolution de réseaux de contraintes par décomposition. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.159-168. ⟨inria-00000073⟩
184 Consultations
31 Téléchargements

Partager

Gmail Facebook X LinkedIn More