Hypercubic Combinatorics: Hamiltonian Decomposition and Permutation Routing

Abstract

In this paper we first present new proofs, much shorter and much simpler than can be found elsewhere, of two facts about Hypercubes: that for the d-dimensional Hypercube, there exists sets of paths by which any permutation routing task may be accomplished in at most 2d - 1 steps without queueing and, when d is even, there exists an edge decomposition of the Hypercube into precisely d/2 edge-disjoint Hamiltonian cycles. The permutation routing paths are computed off-line. Whether or not these paths may be computed by an online parallel algorithm in O(d)-time has long been an open question. We conclude by speculating on whether the use of a Hamiltonian decomposition of the Hypercube might lead to such an algorithm.