Towards a Classification of Hamiltonian Cycles in the 6-Cube.
<p style="text-align:justify;"> In this paper, we consider the problem of classifying Hamiltonian cycles in a binary hypercube. Previous work proposed a classification of these cycles using the edge representation, and presented it for dimension 4. We classify cycles in two further...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
IOS Press
2008
|
| Summary: | <p style="text-align:justify;"> In this paper, we consider the problem of classifying Hamiltonian cycles in a binary hypercube. Previous work proposed a classification of these cycles using the edge representation, and presented it for dimension 4. We classify cycles in two further dimensions using a reduction to propositional SAT. Our proposed algorithm starts with an over-approximation of the set of equivalence classes, which is then refined using queries to a SAT-solver to remove spurious cycles. Our method performs up to three orders of magnitude faster than an enumeration with symmetry breaking in the 5-cube. </p> |
|---|