查看文章

We present a new conceptual abstraction in symmetry breaking–the GE-tree. The construction and traversal of a GE-tree breaks all symmetries in any constraint satisfaction or similar problem. We give a polynomial-time algorithm for this construction in the case of CSPs with arbitrary value symmetries. We have implemented this technique, and supply experimental evidence of its practical effectiveness.