
The Shuffle Exchange Network has a
Hamiltonian Path
Rainer Feldmann Peter Mysliwietz
Department of Mathematics and Computer Science
University of Paderborn, Germany
Preliminary Version
November, 1991
Abstract
We prove the existence of a Hamiltonian path in the Shuffle Exchange network SX(n): This problem has been posed as an open problem by Leighton in [8] and Samatham and Pradhan in [11].
1 Introduction
Parallel computer architectures, as well as data structures, can be described by
networks in a very natural manner. Different networks have been developed for
different applications (see [9] for a survey). For many distributed algorithms running
on a network G; it is helpful, if G has a Hamiltonian cycle or a Hamiltonian path
([12, 11]). The problem to determine whether a network contains a Hamiltonian
path has been a fundamental problem in graph theory (see [7] for a survey).
The most prominent networks that are known to have a Hamiltonian cycle or a
Hamiltonian path are the Hypercube network ([6]), the Cube Connected Cycle network
([12]), the DeBruijn network ([3]), the Butterfly network ([4]) the grid, the
torus and the Shuffle Exchange network of dimension 2d ([5]). Fast algorithms to
determine a Hamiltonian path are known for these networks. In [11], it is noted
that the Shuffle Exchange network suffers from the fact that a Hamiltonian path is
not known for this network in order to run some algorithms as fast as the DeBruijn
network. In [8], Leighton has posed as an open problem to determine whether the
Shuffle Exchange network has a Hamiltonian path.
Often the existence of a Hamiltonian path or cycle has been proved by using some
recursive structure of the network ([6, 12, 3, 5]). Hamiltonian paths (or cycles) are
constructed for small dimensions which can be combined to a Hamiltonian path of
some larger dimension. Sometimes simply showing that a graph which is known
to have a Hamiltonian path or cycle is a subgraph of some other graph yields the
desired result ([4]).