
Open access
Date
2008Type
- Report
ETH Bibliography
yes
Altmetrics
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. Show more
Permanent link
https://doi.org/10.3929/ethz-a-005632646Publication status
publishedJournal / series
Technical Report / ETH Zurich, Department of Computer ScienceVolume
Publisher
ETH, Eidgenössische Technische Hochschule Zürich, Department of Computer ScienceSubject
ZYKLEN (GRAPHENTHEORIE); Bitonic sorting network; CYCLES (GRAPH THEORY); Hypercube; Aymmetry breaking; GRAPHENALGORITHMEN + GEOMETRISCHE ALGORITHMEN (GRAPHENTHEORIE); Code equivalence; Gray code; Hamiltonian cycle; SAT-solver; HYPERGRAPHEN (GRAPHENTHEORIE); GRAPH ALGORITHMS + GEOMETRIC ALGORITHMS (GRAPH THEORY); HYPERGRAPHS (GRAPH THEORY)Organisational unit
02150 - Dep. Informatik / Dep. of Computer Science
Related publications and datasets
Is previous version of: http://hdl.handle.net/20.500.11850/11305
Is identical to: http://hdl.handle.net/20.500.11850/11305
Notes
Technical Reports D-INFK.More
Show all metadata
ETH Bibliography
yes
Altmetrics