Pancake problems with restricted prefix reversals and some corresponding Cayley networks
Cayley networks have desirable properties for interconnection networks, but the degree of many well-known Cayley networks grows with the number of nodes. Therefore, fixed-degree Cayley networks have also been introduced. We consider fixed-degree Cayley networks which are also subnetworks of the pancake network Pn. The pancake problem concerns the number of prefix reversals or flips, required to sort a permutation of length n. This is also the diameter of Pn. Restricting the problem to three of the n?1 possible flips, generates a subnetwork of Pn. We identify proper subnetworks and spanning subnetworks of Pn generated by three flips. We introduce a degree 3 spanning subnetwork of Pn, the Triad network, or Triadn. When n is odd and has n! nodes and diameter . Triadn emulates the shuffle-exchange and shuffle-exchange permutation networks with constant slowdown.
pancake problem cayley networks pancake network diameter spanning subnetworks fixed degree symmetric group routing embeddings