A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations

DOI10.1016/j.jcss.2012.01.005zbMath1244.68088OpenAlexW2047975566MaRDI QIDQ439973

Daming Zhu, Xiaowen Lou

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2012.01.005

zbMATH Keywords

approximation algorithmpermutationtranspositionreversalcut-and-pastetransreversal

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items

A 1.375-approximation algorithm for unsigned translocation sorting

Cites Work

• Unnamed Item
• Unnamed Item
• An approximation algorithm for sorting by reversals and transpositions
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Short proofs for cut-and-paste sorting of permutations
• Sorting by Transpositions Is Difficult
• The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in O(nlogn) Time
• A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations
• A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Sorting by Transpositions
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Combinatorial Pattern Matching
• Signed genome rearrangement by reversals and transpositions: Models and approximations

This page was built for publication: A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations