Skip to Main content Skip to Navigation
Journal articles

Polynomial-time sortable stacks of burnt pancakes

Abstract : Pancake flipping, a famous open problem in computer science, can be formalised as the problem of sorting a permutation of positive integers using as few prefix reversals as possible. In that context, a prefix reversal of length k reverses the order of the first k elements of the permutation. The burnt variant of pancake flipping involves permutations of signed integers, and reversals in that case not only reverse the order of elements but also invert their signs. Although three decades have now passed since the first works on these problems, neither their computational complexity nor the maximal number of prefix reversals needed to sort a permutation is yet known. In this work, we prove a new lower bound for sorting burnt pancakes, and show that an important class of permutations, known as "simple permutations", can be optimally sorted in polynomial time.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00728920
Contributor : Anthony Labarre <>
Submitted on : Friday, September 7, 2012 - 8:58:20 AM
Last modification on : Thursday, June 4, 2020 - 10:24:03 AM
Long-term archiving on: : Saturday, December 8, 2012 - 3:39:56 AM

File

1010.0219v1.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00728920, version 1

Collections

Citation

Anthony Labarre, Josef Cibulka. Polynomial-time sortable stacks of burnt pancakes. Theoretical Computer Science, Elsevier, 2011, 412 (8-10), pp.695-702. ⟨hal-00728920⟩

Share

Metrics

Record views

143

Files downloads

189