Constraints for symmetry breaking in graph representation
Michael Codish, Alice Miller, Patrick Prosser, Peter J Stuckey
CONSTRAINTS | SPRINGER | Published : 2019
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
Awarded by Israel Science Foundation
Codish was supported by the Israel Science Foundation grant 625/17.