The Shuffle Exchange Network has a
Rainer Feldmann Peter Mysliwietz
Department of Mathematics and Computer Science
University of Paderborn, Germany
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  and Samatham and Pradhan in .
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  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  for a survey).
The most prominent networks that are known to have a Hamiltonian cycle or a
Hamiltonian path are the Hypercube network (), the Cube Connected Cycle network
(), the DeBruijn network (), the Butterfly network () the grid, the
torus and the Shuffle Exchange network of dimension 2d (). Fast algorithms to
determine a Hamiltonian path are known for these networks. In , 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 , 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 ().