Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality (Q2689255): Difference between revisions

The authors present four combinatorial algorithms for traversing a specific Hamilton cycle in the \(k\)-sided pancake network. The first one is a min-flip greedy algorithm that requires exponential space to store the network. The second one is a recursive construction that traverses the network in \(O(1)\)-amortized time using linear space, The third one is a successor rule that allows the cycle to be traversed starting from any initial permutation in \(O(1)\)-amortized time per permutation. The fourth one is a loop-free algorithm for the associated flip-sequence. Ranking and unranking algorithms for the Hamiltion cycle with quadratic running time are given for a corresponding listing of coloured permutations. The Hamilton paths and cycles are optimal in terms of minimizing the total number of flips in the coloured pancakes.