Pancake flipping is hard

DOI10.1016/j.jcss.2015.02.003zbMath1328.68084arXiv1111.0434OpenAlexW1846975517WikidataQ56287379 ScholiaQ56287379MaRDI QIDQ494050

Guillaume Fertin, Laurent Bulteau, Irena Rusu

Publication date: 31 August 2015

Published in: Journal of Computer and System Sciences, Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.0434

zbMATH Keywords

permutationscomputational complexitypancake problemprefix reversals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (23)

The spectral gap of graphs arising from substring reversals ⋮ Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals ⋮ Greedy flipping of pancakes and burnt pancakes ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ Prefix and suffix reversals on strings ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ How to sort by walking and swapping on paths and trees ⋮ Prefix and Suffix Reversals on Strings ⋮ Sorting by prefix block-interchanges ⋮ Token Swapping on Trees ⋮ Physical zero-knowledge proof protocol for Topswops ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ Unnamed Item ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Pancake flipping and sorting permutations ⋮ Pancake flipping is hard ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Dynamically improved bounds bidirectional search ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ Cycles in the burnt pancake graph ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ Some relations on prefix reversal generators of the symmetric and hyperoctahedral group ⋮ An Audit Tool for Genome Rearrangement Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Pancake flipping is hard
• Polynomial-time sortable stacks of burnt pancakes
• On average and highest number of flips in pancake sorting
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Bounds for sorting by prefix reversal
• On the problem of sorting burnt pancakes
• Transforming cabbage into turnip
• A group-theoretic model for symmetric interconnection networks
• On the Diameter of the Pancake Network
• Genome Rearrangements and Sorting by Reversals
• Algorithms – ESA 2005

This page was built for publication: Pancake flipping is hard