COMPUTER VERIFICATION OF THE RESULTS ON THE DIAMETER OF THE N-DIMENSIONAL PAN CAKE NETWORKS

Marissa P. Justan
H. Benton Ellis Computer Center
Trinity College, Quezon City, Philippines
trinity@galileo.fapenet.org

Abstract

The n-dimensional Pancake Network, Pn, has processors labeled with each of the n! distinct permutations of length n. A link between two processors is obtained when the label of one is derived from the other by some prefix reversal. Each permutation is considered as a stack of different size pancakes. The well known pancake problem concerns the number, f(n), of prefix reversals required to sort n pancakes. The most recent (1996) results revealed values of f(n) for n < 14. Validation by computers rapidly becomes unworkable for n > 10. The immediately limiting resource is actually the large space requirement of a breadth first search on the group. In this paper we attempt to work around this restriction.