Optimal symmetry breaking for graph problems

DOI10.1007/s11786-019-00397-5zbMath1474.68225OpenAlexW2945470040MaRDI QIDQ2009225

Marijn J. H. Heule

Publication date: 27 November 2019

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11786-019-00397-5

zbMATH Keywords

graphssymmetry breakingsatisfiability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

Related Items (1)

Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs

Uses Software

• sharpSAT
• bliss

Cites Work

• Unnamed Item
• Unnamed Item
• Small Ramsey numbers
• Satisfiability and computing van der Waerden numbers
• Breaking symmetries in graph search with canonizing sets
• Computing the Ramsey number \(R(4,3,3)\) using abstraction and symmetry breaking
• Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer
• A SAT Attack on the Erdős Discrepancy Conjecture
• SAT-Based Formula Simplification
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• The van der Waerden NumberW(2, 6) Is 1132
• R(4, 5) = 25
• Green-Tao Numbers and SAT
• Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs

This page was built for publication: Optimal symmetry breaking for graph problems