Breaking Symmetries in Graph Representation
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 510-515.
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.
@inproceedings{ijcai2013p83,
title = {Breaking Symmetries in Graph Representation},
author = {Codish, Michael and Miller, Alice and Prosser, Patrick and Stuckey, Peter J.},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {510--515},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/83},
}
TY - CPAPER TI - Breaking Symmetries in Graph Representation AU - Codish, Michael AU - Miller, Alice AU - Prosser, Patrick AU - Stuckey, Peter J. T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 510 EP - 515 UR - https://ijcai.org/proceedings/2013/83 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
