Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs

DOI10.1007/S10601-021-09323-8MaRDI QIDQ2152271zbMATH OpenOpenAlexWikidataFDO

Authors Avraham Itzhakov, Michael Codish

Publication date 7 July 2022

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10601-021-09323-8

zbMATH Keywords

constraint programmingisomorph-free graph generationsymmetry breakinguniquely Hamiltonian graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• Breaking symmetries in graph search with canonizing sets
• Constraints for symmetry breaking in graph representation
• Generating effective symmetry-breaking predicates for search problems
• Optimal symmetry breaking for graph problems
• A degree constraint for uniquely Hamiltonian graphs

Cites work

• Boolean equi-propagation for concise and efficient SAT encodings of combinatorial problems
• Breaking symmetries in graph search with canonizing sets
• Breaking symmetries with lex implications
• Cataloguing the graphs on 10 vertices
• Compiling finite domain constraints to SAT with BEE
• Computing the Ramsey number \(R(4,3,3)\) using abstraction and symmetry breaking
• Constraints for symmetry breaking in graph representation
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Extremal graphs without three‐cycles or four‐cycles
• General Symmetry Breaking Constraints
• Generating effective symmetry-breaking predicates for search problems
• Graphs with exactly one hamiltonian circuit
• Graphs with few Hamiltonian cycles
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• Isomorph-Free Exhaustive Generation
• On uniquely Hamiltonian claw-free and triangle-free graphs
• Optimal symmetry breaking for graph problems
• Practical graph isomorphism. II.
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• Uniquely Hamiltonian graphs of minimum degree 4
• Vertices of small degree in uniquely Hamiltonian graphs

Cited in

(2)

• Generating streamlining constraints with large language models
• Symmetry classes of Hamiltonian cycles

Describes a project that uses

Uses Software

• nauty
• MathOverflow
• Glucose
• BEE
• OEIS
• Traces
• GenerateUHG

This page was built for publication: Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2152271)