SODA

Arc-Consistency for a Chain of Lexicographic Ordering Constraints

Carlsson, Mats and Beldiceanu, Nicolas (2002) Arc-Consistency for a Chain of Lexicographic Ordering Constraints. [SICS Report]

[img]
Preview
PDF
162Kb
[img]Postscript
100Kb

Abstract

We present an arc-consistency algorithm for a chain of lexicographic ordering constraints on $m$ vectors of $n$ variables each. The algorithm maintains arc-consistency and runs in $O(nmd)$ time per invocation, where $d$ is the cost of certain domain operations.

Item Type:SICS Report
Uncontrolled Keywords:Constraint Programming, Global Constraints, Lexicographic Ordering, Symmetry
ID Code:2267
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:03

Repository Staff Only: item control page