Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

https://hal.inria.fr/inria-00000073
Contributor : Christine Solnon <>
Submitted on : Thursday, May 26, 2005 - 11:28:50 AM
Last modification on : Monday, March 30, 2020 - 8:53:18 AM
Long-term archiving on: : Thursday, April 1, 2010 - 9:33:32 PM

Files

Identifiers

  • HAL Id : inria-00000073, version 1

Citation

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⟩

Share

Metrics

Record views

112

Files downloads

217