Breaking symmetries in graph representation

Michael Codish, Alice Miller, Patrick Prosser, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationIJCAI 2013 - Proceedings of the 23rd International Joint Conference on Artificial Intelligence
Pages510-516
Number of pages7
Publication statusPublished - 1 Dec 2013
Externally publishedYes
EventInternational Joint Conference on Artificial Intelligence 2013 - Beijing, China
Duration: 3 Aug 20139 Aug 2013
Conference number: 23rd
http://ijcai-13.org/
https://www.ijcai.org/proceedings/2013 (conference proceedings)

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2013
Abbreviated titleIJCAI 2013
CountryChina
CityBeijing
Period3/08/139/08/13
Internet address

Cite this

Codish, M., Miller, A., Prosser, P., & Stuckey, P. J. (2013). Breaking symmetries in graph representation. In IJCAI 2013 - Proceedings of the 23rd International Joint Conference on Artificial Intelligence (pp. 510-516). (IJCAI International Joint Conference on Artificial Intelligence).