Constraint propagation for loose constraint graphs

Kathryn Francis, Peter J. Stuckey

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

1 Citation (Scopus)

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, South
Duration: 11 Mar 200715 Mar 2007
Conference number: 22nd
https://dl.acm.org/doi/proceedings/10.1145/1244002 (Proceedings)

Conference

ConferenceACM Symposium on Applied Computing 2007
Abbreviated titleSAC 2007
Country/TerritoryKorea, South
CitySeoul
Period11/03/0715/03/07
Internet address

Keywords

  • Constraint graph
  • Constraint propagation

Cite this