Pancake flipping and sorting permutations

DOI10.1016/j.jda.2015.03.007zbMath1329.68289MaRDI 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 algorithms; genome sorting; pancake flipping; sorting permutations

Mathematics Subject Classification ID

68P10: Searching and sorting

05A05: Permutations, words, matrices

92D10: Genetics and epigenetics

68W25: Approximation algorithms

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