Pancake flipping and sorting permutations
From MaRDI portal
Publication:491630
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
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