Towards a Classification of Hamiltonian Cycles in the 6-Cube
OPEN ACCESS
Loading...
Author / Producer
Date
2007
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Abstract
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.
Permanent link
Publication status
published
External links
Editor
Book title
Volume
4 (1)
Pages / Article No.
57 - 74
Publisher
University of Delft
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
bitonic sorting network; code equivalence; Gray code; Hamiltonian cycle; hypercube; SAT-solver; symmetry breaking
Organisational unit
03686 - Kröning, Daniel (ehemalig)
Notes
Funding
Related publications and datasets
Is identical to: 10.3929/ethz-a-005632646