Hamiltonicity of k-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
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.
- A group-theoretic model for symmetric interconnection networks
- A Hamilton cycle in the \(k\)-sided pancake network
- A new algorithm for generation of permutations
- Binomial Eulerian polynomials for colored permutations
- Bounds for sorting by prefix reversal
- Coloured permutations containing and avoiding certain patterns
- Combinatorial generation via permutation languages
- Combinatorial generation via permutation languages. I: Fundamentals
- Combinatorics of genome rearrangements.
- Fabian Stedman: The First Group Theorist?
- Fun with algorithms. 5th international conference, FUN 2010, Ischia, Italy, June 2--4, 2010. Proceedings
- Fun with algorithms. 7th international conference, FUN 2014, Lipari Island, Sicily, Italy, July 1--3, 2014. Proceedings
- Generation of permutation sequences: Part 2
- Generation of Permutations by Adjacent Transposition
- Greedy flipping of pancakes and burnt pancakes
- scientific article; zbMATH DE number 3557795 (Why is no real title available?)
- scientific article; zbMATH DE number 706769 (Why is no real title available?)
- scientific article; zbMATH DE number 3189338 (Why is no real title available?)
- Labeled partitions with colored permutations
- Longest increasing subsequences of random colored permutations
- Minimal overlapping patterns in colored permutations
- On the Diameter of the Pancake Network
- On the group of alternating colored permutations.
- On the problem of sorting burnt pancakes
- Pattern avoidance in coloured permutations
- Perfect Snake-in-the-Box Codes for Rank Modulation
- Successor rules for flipping pancakes and burnt pancakes
- Symmetric unimodal expansions of excedances in colored permutations
- The greedy Gray code algorithm
- The spurs of D. H. Lehmer. Hamiltonian paths in neighbor-swap graphs of permutations
- Constant time and space updates for the sigma-tau problem
- Generating signed permutations by twisting two-sided ribbons
- Maximize the rightmost digit: Gray codes for restricted growth strings
- Skipping ropes: an efficient gray code algorithm for generating wiggly permutations
- Successor rules for flipping pancakes and burnt pancakes
This page was built for publication: Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2689255)
