Hamiltonicity of k-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality

DOI10.1007/S00453-022-01022-XOpenAlexW4292607711MaRDI QIDQ2689255FDOQ2689255

Authors: Ben Cameron, Joe Sawada, Wei Therese, Aaron Williams 

Publication date: 9 March 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01022-x

Recommendations

• Successor rules for flipping pancakes and burnt pancakes
• Greedy flipping of pancakes and burnt pancakes
• On the Diameter of the Pancake Network
• Cycles in the burnt pancake graph
• Small cycles in the pancake graph

zbMATH Keywords

greedy algorithmHamilton cyclecombinatorial generation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• A group-theoretic model for symmetric interconnection networks
• Combinatorics of genome rearrangements.
• Bounds for sorting by prefix reversal
• The greedy Gray code algorithm
• Greedy flipping of pancakes and burnt pancakes
• Title not available (Why is that?)
• On the Diameter of the Pancake Network
• Generation of Permutations by Adjacent Transposition
• A new algorithm for generation of permutations
• Successor rules for flipping pancakes and burnt pancakes
• Symmetric unimodal expansions of excedances in colored permutations
• Fun with algorithms. 7th international conference, FUN 2014, Lipari Island, Sicily, Italy, July 1--3, 2014. Proceedings
• Coloured permutations containing and avoiding certain patterns
• Pattern avoidance in coloured permutations
• Minimal overlapping patterns in colored permutations
• On the problem of sorting burnt pancakes
• On the group of alternating colored permutations.
• Fun with algorithms. 5th international conference, FUN 2010, Ischia, Italy, June 2--4, 2010. Proceedings
• Longest increasing subsequences of random colored permutations
• Title not available (Why is that?)
• Perfect Snake-in-the-Box Codes for Rank Modulation
• Combinatorial generation via permutation languages
• Binomial Eulerian polynomials for colored permutations
• Title not available (Why is that?)
• Labeled partitions with colored permutations
• Generation of permutation sequences: Part 2
• A Hamilton cycle in the \(k\)-sided pancake network
• The spurs of D. H. Lehmer. Hamiltonian paths in neighbor-swap graphs of permutations
• Combinatorial generation via permutation languages. I: Fundamentals
• Fabian Stedman: The First Group Theorist?

Cited In (3)

• Successor rules for flipping pancakes and burnt pancakes
• Constant time and space updates for the sigma-tau problem
• Generating signed permutations by twisting two-sided ribbons

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)