Polynomial-time sortable stacks of burnt pancakes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10100844" target="_blank" >RIV/00216208:11320/11:10100844 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2010.11.004" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2010.11.004</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2010.11.004" target="_blank" >10.1016/j.tcs.2010.11.004</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Polynomial-time sortable stacks of burnt pancakes

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Polynomial-time sortable stacks of burnt pancakes

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GD201%2F09%2FH057" target="_blank" >GD201/09/H057: Res Informatica</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

412

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

8

Strana od-do

695-702

Kód UT WoS článku

000287295000007

EID výsledku v databázi Scopus

—