Constraint propagation for loose constraint graphs

Kathryn Francis; Peter J. Stuckey

doi:10.1145/1244002.1244081

Constraint propagation for loose constraint graphs

Kathryn Francis, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Proceedings of the 2007 ACM Symposium on Applied Computing
Pages	334-335
Number of pages	2
DOIs	https://doi.org/10.1145/1244002.1244081
Publication status	Published - 18 Oct 2007
Externally published	Yes
Event	ACM Symposium on Applied Computing 2007 - Seoul, Korea, South Duration: 11 Mar 2007 → 15 Mar 2007 Conference number: 22nd https://dl.acm.org/doi/proceedings/10.1145/1244002 (Proceedings)

Conference

Conference	ACM Symposium on Applied Computing 2007
Abbreviated title	SAC 2007
Country/Territory	Korea, South
City	Seoul
Period	11/03/07 → 15/03/07
Internet address	https://dl.acm.org/doi/proceedings/10.1145/1244002 (Proceedings)

Keywords

Constraint graph
Constraint propagation

Access to Document

10.1145/1244002.1244081

Cite this

@inproceedings{cb99ad5ea6f24be8be38fed823530708,

title = "Constraint propagation for loose constraint graphs",

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.",

keywords = "Constraint graph, Constraint propagation",

author = "Kathryn Francis and Stuckey, {Peter J.}",

year = "2007",

month = oct,

day = "18",

doi = "10.1145/1244002.1244081",

language = "English",

isbn = "1595934804",

pages = "334--335",

booktitle = "Proceedings of the 2007 ACM Symposium on Applied Computing",

note = "ACM Symposium on Applied Computing 2007, SAC 2007 ; Conference date: 11-03-2007 Through 15-03-2007",

url = "https://dl.acm.org/doi/proceedings/10.1145/1244002",

}

TY - GEN

T1 - Constraint propagation for loose constraint graphs

AU - Francis, Kathryn

AU - Stuckey, Peter J.

N1 - Conference code: 22nd

PY - 2007/10/18

Y1 - 2007/10/18

N2 - 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.

AB - 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.

KW - Constraint graph

KW - Constraint propagation

UR - http://www.scopus.com/inward/record.url?scp=35248846907&partnerID=8YFLogxK

U2 - 10.1145/1244002.1244081

DO - 10.1145/1244002.1244081

M3 - Conference Paper

AN - SCOPUS:35248846907

SN - 1595934804

SN - 9781595934802

SP - 334

EP - 335

BT - Proceedings of the 2007 ACM Symposium on Applied Computing

T2 - ACM Symposium on Applied Computing 2007

Y2 - 11 March 2007 through 15 March 2007

ER -

Constraint propagation for loose constraint graphs

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this