Journal article

Constraints for symmetry breaking in graph representation

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

CONSTRAINTS | SPRINGER | Published : 2019

Abstract

Many complex combinatorial problems arising from a range of scientific applications (such as computer networks, mathematical chemistry and bioinformatics) involve searching for an undirected graph satisfying a given property. Since for any possible solution there can be a large number of isomorphic representations, these problems can quickly become intractable. One way to mitigate this problem is to eliminate as many isomorphic copies as possible by breaking symmetry during search - i.e. by introducing constraints that ensure that at least one representative graph is generated for each equivalence class, but not the entire class. The goal is to generate as few members of each class as possib..

View full abstract

Grants

Awarded by Israel Science Foundation


Funding Acknowledgements

Codish was supported by the Israel Science Foundation grant 625/17.