Pancake flipping and sorting permutations

DOI10.1016/J.JDA.2015.03.007MaRDI QIDQ491630zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Prefix Reversals on Binary and Ternary Strings
• Sorting by prefix reversals and prefix transpositions
• An (18/11)n upper bound for sorting by prefix reversals
• Prefix Reversals on Binary and Ternary Strings
• Algorithms – ESA 2005

Cites work

• scientific article; zbMATH DE number 1263193 (Why is no real title available?)
• scientific article; zbMATH DE number 1947393 (Why is no real title available?)
• scientific article; zbMATH DE number 1405677 (Why is no real title available?)
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations
• A simpler 1.5-approximation algorithm for sorting by transpositions
• Algorithms – ESA 2005
• An approximation algorithm for sorting by reversals and transpositions
• Bounds for sorting by prefix reversal
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Genome Rearrangements and Sorting by Reversals
• On the Diameter of the Pancake Network
• Pancake problems with restricted prefix reversals and some corresponding Cayley networks.
• Sorting by Transpositions
• (1+)-approximation of sorting by reversals and transpositions.

Cited in

(2)

• An (18/11)n upper bound for sorting by prefix reversals
• Prefix Reversals on Binary and Ternary Strings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491630)