Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality (Q2689255)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality |
scientific article |
Statements
Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality (English)
0 references
9 March 2023
0 references
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.
0 references
Hamilton cycle
0 references
combinatorial generation
0 references
greedy algorithm
0 references
0 references