= Full-sweep arc consistency
Compute an <arc-consistency closure> by revising every directed constrained pair in complete sweeps until one sweep deletes nothing. The first sweep is unconditional. With $v$ variables, maximum <constraint domain> size $d$, and $e$ constrained pairs, at most $vd$ deletions permit at most $vd+1$ sweeps. At $O(d^2)$ per revision plus $O(v)$ per emptiness scan, a direct <time complexity> bound is $O((vd+1)(ed^2+v))$. <AC-3> uses a work list to avoid scanning unrelated arcs after each local change.
Back to article page
