Dynamic Symmetry Breaking by Simulating Zykov Contraction

DOI10.1007/978-3-642-02777-2_22zbMath1247.68260OpenAlexW2130088495MaRDI QIDQ3637171

Hans van Maaren, Bas Schaafsma, Marijn J. H. Heule

Publication date: 7 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02777-2_22

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (4)

Expressing Symmetry Breaking in DRAT Proofs ⋮ Constraint and Satisfiability Reasoning for Graph Coloring ⋮ An adaptive prefix-assignment technique for symmetry reduction ⋮ Improved Static Symmetry Breaking for SAT

Uses Software

• MiniSat
• Chaff

Cites Work

• Unnamed Item
• A structure-preserving clause form translation
• Exploiting multivalued knowledge in variable selection heuristics for SAT solvers
• Another look at graph coloring via propositional satisfiability
• Extended Resolution Proofs for Conjoining BDDs
• Hard examples for resolution
• Theory and Applications of Satisfiability Testing
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: Dynamic Symmetry Breaking by Simulating Zykov Contraction