A quadratic time 2-approximation algorithm for block sorting

DOI10.1016/j.tcs.2008.10.022zbMath1162.68008OpenAlexW2044323551MaRDI QIDQ1006043

Linda Morales, Wolfgang W. Bein, Lawrence L. Larmore, Ivan Hal Sudborough

Publication date: 17 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.022

zbMATH Keywords

approximation algorithmsoptical character recognitiondesign and analysis of algorithmsblock sortingtransposition sorting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Pattern recognition, speech recognition (68T10) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Related Items (1)

Block Sorting Is APX-Hard

Cites Work

• Unnamed Item
• Bounds for sorting by prefix reversal
• Sorting by bounded block-moves
• Sorting by short block-moves
• On the Diameter of the Pancake Network
• Sorting by Transpositions
• Computing and Combinatorics
• Genome Rearrangements and Sorting by Reversals
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• APPROXIMATE BLOCK SORTING
• Fundamentals of Computation Theory
• Block Sorting is Hard

This page was built for publication: A quadratic time 2-approximation algorithm for block sorting