 |
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
Abstract:
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
mcodish@cs.bgu.ac.il