Report Number: CS-TR-85-1050
Institution: Stanford University, Department of Computer Science
Title: Fast sequential algorithms to find shuffle-minimizing and shortest paths in a shuffle-exchange network
Author: Hershberger, John
Author: Mayr, Ernst
Date: May 1985
Abstract: This paper analyzes the problem of finding shortest paths and shuffle-minimizing paths in an n-node shuffle-exchange network, where n = $2^m$. Such paths have the properties needed by the Valiant-Brebner permutation routing algorithm, unlike the trivial (m - 1)-shuffle paths usually used for shuffle-exchange routing. The Valiant-Brebner algorithm requires n simultaneous route computations, one for each packet to be routed, which can be done in parallel. We give fast sequential algorithms for both problems we consider. Restricting the shortest path problem to allow only paths that use fewer than m shuffles provides intuition applicable to the general problem. Linear-time pattern matching techniques solve part of the restricted problem; as a consequence, a path using fewest shuffles can be found in O(m) time, which is optimal up to a constant factor. The shortest path problem is equivalent to the problem of finding the Hamming distances between a bitstring and all shifted instances of another. An application of the fast Fourier transform solves this problem and the shortest path problem in O(m log m) time.
http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1050/CS-TR-85-1050.pdf