Constraint propagation for loose constraint graphs

Kathryn Francis, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

In this paper we investigate how to improve propagation-based finite domain constraint solving by making use of the constraint graph to choose propagators to execute in a better order. If the constraint graph is not too densely connected we can build an underlying tree of bi-connected components, and use this to order the choice of propagator. Our experiments show that there exist problems where handling biconnected components can substantially improve the propagation performance.

Original languageEnglish
Title of host publicationProceedings of the 2007 ACM Symposium on Applied Computing
Pages334-335
Number of pages2
DOIs
Publication statusPublished - 18 Oct 2007
Externally publishedYes
EventACM Symposium on Applied Computing 2007 - Seoul, Korea, Republic of (South)
Duration: 11 Mar 200715 Mar 2007

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Conference

ConferenceACM Symposium on Applied Computing 2007
CountryKorea, Republic of (South)
CitySeoul
Period11/03/0715/03/07

Keywords

  • Constraint graph
  • Constraint propagation

Cite this

Francis, K., & Stuckey, P. J. (2007). Constraint propagation for loose constraint graphs. In Proceedings of the 2007 ACM Symposium on Applied Computing (pp. 334-335). (Proceedings of the ACM Symposium on Applied Computing). https://doi.org/10.1145/1244002.1244081