A 14/11-approximation algorithm for sorting by short block-moves

DOI10.1007/s11432-010-4131-5zbMath1214.68464MaRDI QIDQ543206

Daming Zhu, Haitao Jiang

Publication date: 17 June 2011

Published in: Science China. Information Sciences (Search for Journal in Brave)

Full work available at URL: http://engine.scichina.com/doi/10.1007/s11432-010-4131-5

zbMATH Keywords

approximation algorithm; short block-move

Mathematics Subject Classification ID

68W40: Analysis of algorithms

92D10: Genetics and epigenetics

68W25: Approximation algorithms

Related Items

Quasi-linear modeling of gyroresonance between different MLT chorus and geostationary orbit electrons, A cost-sharing method for the multi-level economic lot-sizing game, Sorting a permutation by best short swaps, Approximation algorithms for sorting by bounded singleton moves, An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of unsigned translocation distance
• Sorting by bounded block-moves
• Sorting by short block-moves
• Transforming cabbage into turnip
• A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• Theory and Applications of Models of Computation
• Polynomial-time algorithm for computing translocation distance between genomes