On the speed of constraint propagation and the time complexity of arc consistency testing

Christoph Berkholz, Oleg Verbitsky

Establishing arc consistency on two relational structures is one of the most popular heuristics for the constraint satisfaction problem. We aim at determining the time complexity o…