Breaking Symmetries in Graph Representation

Michael Codish, Alice Miller, Patrick Prosser and Peter Stuckey   

IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence; 2013


There are many complex combinatorial problems which involve searching for an undirected graph satisfying a certain property. These problems are often highly challenging because of the large number of isomorphic representations of a possible solution. In this paper we introduce novel, effective and compact, symmetry breaking constraints for undirected graph search. While incomplete, these prove highly beneficial in pruning the search for a graph. We illustrate the application of symmetry breaking in graph representation to resolve several open instances in extremal graph theory.

Available:    bibtex entry   pdf

Related sites:   Online Proceedings

Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel

© copyright notice