page 1  (17 pages)
2to next section

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


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]).