ECAI 2004 Conference Paper

Tractable symmetry breaking using restricted search trees

Colva M. Roney-Dougal, Ian P. Gent, Tom Kelsey, Steve Linton

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.

Keywords: Symmetry, Constraints, Search

Citation: Colva M. Roney-Dougal, Ian P. Gent, Tom Kelsey, Steve Linton: Tractable symmetry breaking using restricted search trees. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.211-215.

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).