Pancake flipping and sorting permutations

DOI10.1016/j.jda.2015.03.007zbMath1329.68289OpenAlexW2071070163MaRDI QIDQ491630

Rukhsana Yeasmin, Masud Hasan, Mahfuza Sharmin, M. Sohel Rahman, Md. Khaledur Rahman, Atif Rahman

Publication date: 18 August 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.03.007

zbMATH Keywords

approximation algorithmsgenome sortingpancake flippingsorting permutations

Mathematics Subject Classification ID

Searching and sorting (68P10) Permutations, words, matrices (05A05) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pancake flipping is hard
• An approximation algorithm for sorting by reversals and transpositions
• Bounds for sorting by prefix reversal
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Pancake problems with restricted prefix reversals and some corresponding Cayley networks.
• \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations
• A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
• On the Diameter of the Pancake Network
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• Algorithms – ESA 2005

This page was built for publication: Pancake flipping and sorting permutations