Pancake Flipping with Two Spatulas

Simple item page
dc.creatorHasan, Masud
dc.creatorRahman, Atif
dc.creatorRahman, M. Sohel
dc.creatorSharmin, Mahfuza
dc.creatorYeasmin, Rukhsana
dc.date2008-12-20
dc.date2009-05-04
dc.date.accessioned2026-07-07T13:10:53Z
dc.date.available2026-07-07T13:10:53Z
dc.descriptionIn this paper we study several variations of the \emph{pancake flipping problem}, which is also well known as the problem of \emph{sorting by prefix reversals}. We consider the variations in the sorting process by adding with prefix reversals other similar operations such as prefix transpositions and prefix transreversals. These type of sorting problems have applications in interconnection networks and computational biology. We first study the problem of sorting unsigned permutations by prefix reversals and prefix transpositions and present a 3-approximation algorithm for this problem. Then we give a 2-approximation algorithm for sorting by prefix reversals and prefix transreversals. We also provide a 3-approximation algorithm for sorting by prefix reversals and prefix transpositions where the operations are always applied at the unsorted suffix of the permutation. We further analyze the problem in more practical way and show quantitatively how approximation ratios of our algorithms improve with the increase of number of prefix reversals applied by optimal algorithms. Finally, we present experimental results to support our analysis.
dc.description10 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/0812.3933
dc.identifierhttp://arxiv.org/abs/0812.3933
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/229124
dc.subjectData Structures and Algorithms
dc.subjectOther Computer Science
dc.titlePancake Flipping with Two Spatulas
dc.typetext

Files

Collections

arXiv