will lead to a node other than T0, because then there is at least one satisfying path to T1 allowing xi = j.

T raverse(**u, j**)
1: i ← var1(u)
2: v0, . . . , vki−1 ← enc(j)
3: s ← var2(u)
4: if **Marked**[u] = j **return** T0 5: **Marked**[u] ← j 6: while s ≤ ki − 1 7: if var1(u) > i **return** u 8: if vs = 0 u ← low(u)
10: else u ← **high**(u)
12: if **Marked**[u] = j **return** T0 13: **Marked**[u] ← j 14: s ← var2(u)
Fig. 7. For fixed u ∈ V, i = var1(u), T raverse(**u, j**) iterates through Vi and returns the node in which the traversal ends up.

When traversing with T raverse(**u, j**) we mark the already traversed nodes ut with j, **M arked**[ut] ← j and prevent processing them again in the future j-traversals T raverse(u
′
, j). Namely, if T raverse(**u, j**) reached T0 node through ut, then any other traversal **T raverse**(u
′
, j) reaching ut must as well end up in T0. Therefore, for every value j ∈ Di, every node u ∈ Viis traversed at most once, leading to worst case running time complexity of O(|Vi|·|Di|). Hence, the total running time for all variables is O(Pn−1 i=0 |Vi**| · |**Di|).

The total worst-case running time for the two **CV D** algorithms is therefore O(Pn−1 i=0 |Vi|·
|Di| + |E| + n) = O(Pn−1 i=0 |Vi**| · |**Di| + n).

## References

1. Jensen, R.M.: CLab: A C++ library for fast backtrack-free interactive product configuration.

http://www.itu.dk/people/rmj/clab/ (2007)
2. Raskin, J.: The Humane Interface. Addison Wesley (2000)
3. Amilhastre, J., Fargier, H., Marquis, P.: Consistency restoration and explanations in dynamic CSPs-application to configuration. Artificial Intelligence 1-2 (2002) 199–234 ftp://fpt.irit.fr/pub/IRIT/RPDMP/Configuration/.

4. Madsen, J.N.: Methods for interactive constraint satisfaction. Master's thesis, Department of Computer Science, University of Copenhagen (2003)
5. Hadzic, T., Subbarayan, S., Jensen, R.M., Andersen, H.R., Møller, J., Hulgaard, H.: Fast backtrack-free product configuration using a precompiled solution space representation. In: PETO Conference, DTU-tryk (2004) 131–138 6. Møller, J., Andersen, H.R., Hulgaard, H.: Product configuration over the internet. In: Proceedings of the 6th INFORMS Conference on Information Systems and Technology. (2002)
7. Configit Software A/S. **http://www.configit-software.com** (online)