On average and highest number of flips in pancake sorting

DOI10.1016/j.tcs.2010.11.028zbMath1211.68138OpenAlexW2129810020MaRDI QIDQ627182

Josef Cibulka

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.028

zbMATH Keywords

permutationsaverage-case analysispancake problemprefix reversalsburnt pancake problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items (12)

Greedy flipping of pancakes and burnt pancakes ⋮ Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ Pancake flipping is hard ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ On Some Structural Properties of Star and Pancake Graphs ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ Cycles in the burnt pancake graph ⋮ Some relations on prefix reversal generators of the symmetric and hyperoctahedral group ⋮ A new general family of mixed graphs ⋮ Neighbor connectivity of pancake graphs and burnt pancake graphs ⋮ Fault tolerance and diagnosability of burnt pancake networks under the comparison model

Cites Work

• An \((18/11)n\) upper bound for sorting by prefix reversals
• Bounds for sorting by prefix reversal
• On the problem of sorting burnt pancakes
• On the Diameter of the Pancake Network
• Unnamed Item

This page was built for publication: On average and highest number of flips in pancake sorting