Breaking symmetries in graph search with canonizing sets

DOI10.1007/s10601-016-9244-zzbMath1368.90137arXiv1511.08205OpenAlexW2270972703MaRDI QIDQ2398437

Michael Codish, Avraham Itzhakov

Publication date: 16 August 2017

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.08205

zbMATH Keywords

symmetry breakingSAT solvinggraph search problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (3)

Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs ⋮ Optimal symmetry breaking for graph problems ⋮ An adaptive prefix-assignment technique for symmetry reduction

Uses Software

• nauty
• OEIS
• Glucose
• Easychair
• Saucy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of symmetry-breaking formulas
• Degree sequences of highly irregular graphs
• Small Ramsey numbers
• Constraints for symmetry breaking in graph representation
• Generating effective symmetry-breaking predicates for search problems
• Conflict Anticipation in the Search for Graph Automorphisms
• General Symmetry Breaking Constraints
• Cataloguing the graphs on 10 vertices
• Highly irregular graphs
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Isomorph-Free Exhaustive Generation
• R(4, 5) = 25
• Fast generation of cubic graphs
• Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems
• Symmetry and Satisfiability: An Update
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: Breaking symmetries in graph search with canonizing sets