A time-space trade-off for constraint networks decomposition

We study here a CSP decomposition method introduced in [P. Jegou (1990)] and called cyclic-clustering. While [P. Jegou (1990)] only presents the principles of the method, This work explains how this method can be made operational by exploiting good properties have triangulated induced subgraphs. After, we give formal results, which show that cyclic-clustering proposes a time-space trade-off w.r.t. theoretical complexities. Finally, we present some preliminary experiments, which show that cyclic-clustering may be efficient in practice.