Constraints for symmetry breaking in graph representation

DOI10.1007/s10601-018-9294-5zbMath1425.05099OpenAlexW2888038357MaRDI QIDQ2331101

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

Publication date: 25 October 2019

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: http://eprints.gla.ac.uk/165865/7/165865.pdf

zbMATH Keywords

constraints and satisfiabilitysymmetry and search

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs ⋮ Breaking symmetries in graph search with canonizing sets ⋮ Computing the Ramsey number \(R(4,3,3)\) using abstraction and symmetry breaking ⋮ Breaking symmetries with high dimensional graph invariants and their combination ⋮ Finding the Hardest Formulas for Resolution ⋮ Induction and Exploitation of Subgoal Automata for Reinforcement Learning

Uses Software

• nauty
• OEIS
• Traces
• CryptoMiniSat
• BEE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact values of \(ex(\nu ; \{C_{3},C_{4},\dots ,C_n\})\)
• New families of graphs without short cycles and large size
• On the complexity of submap isomorphism and maximum common submap problems
• Some new upper bounds of \(\operatorname{ex}(n;\{C_3,C_4\})\)
• Computing the Ramsey number \(R(4,3,3)\) using abstraction and symmetry breaking
• Practical graph isomorphism. II.
• On extremal unicyclic molecular graphs with prescribed girth and minimal Hosoya index
• Generating effective symmetry-breaking predicates for search problems
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Extremal graphs without three‐cycles or four‐cycles
• Algorithms and complexity results for finding graphs with extremal Randić index
• Compiling finite domain constraints to SAT withBEE
• On the maximal triangle-free edge-chromatic graphs in three colors
• Principles and Practice of Constraint Programming – CP 2003
• Using simulated annealing to construct extremal graphs
• Exploiting symmetries within constraint satisfaction search

This page was built for publication: Constraints for symmetry breaking in graph representation