Breaking Symmetries in Graph Representation
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.
Cite
Text
Codish et al. "Breaking Symmetries in Graph Representation." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Codish et al. "Breaking Symmetries in Graph Representation." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/codish2013ijcai-breaking/)BibTeX
@inproceedings{codish2013ijcai-breaking,
title = {{Breaking Symmetries in Graph Representation}},
author = {Codish, Michael and Miller, Alice and Prosser, Patrick and Stuckey, Peter James},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {510-516},
url = {https://mlanthology.org/ijcai/2013/codish2013ijcai-breaking/}
}