Propagation Rules for Graph Partitioning Constraints
Radosław Cymer
Vol. 20, no. 2, pp. 363-410, 2016. Regular paper.
Abstract We review existing methods and present a generic propagation mechanism for graph partitioning constraints based on directed matchings. The task is also to give a set of several propagation rules according to specific partition properties. Every solution of the global constraint corresponds to a subgraph of the corresponding digraph associated with the constraint. The filtering identifies the arcs of the digraph that do not belong to a solution. We illustrate this principle on some common global constraints.
Submitted: October 2015.
Reviewed: April 2016.
Revised: May 2016.
Accepted: May 2016.
Final: June 2016.
Published: June 2016.
Communicated by Giuseppe Liotta
article (PDF)