Block Sorting is Hard

DOI10.1142/S0129054103001820MaRDI QIDQ5696919zbMATH OpenFDO

Authors Lawrence L. Larmore, Shahram Latifi, Wolfgang W. Bein, I. H. Sudborough

Publication date 19 October 2005

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054103001820

zbMATH Keywords

\(\mathcal {NP}\)-completenessblock sortingoptical character recognitionoptimal sorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Pattern recognition, speech recognition (68T10)

Recommendations

• Block Sorting Is APX-Hard
• Fundamentals of Computation Theory
• Block sorting: a characterization and some heuristics
• APPROXIMATE BLOCK SORTING
• A quadratic time 2-approximation algorithm for block sorting

Cites work

• Bounds for sorting by prefix reversal
• Genome Rearrangements and Sorting by Reversals
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the Diameter of the Pancake Network
• Sorting by bounded block-moves
• Sorting by short block-moves
• Sorting by Transpositions

Cited in

(8)

• A quadratic time 2-approximation algorithm for block sorting
• Optimal narrowing of a block of sortings in optimal time
• Block Sorting Is APX-Hard
• APPROXIMATE BLOCK SORTING
• Fundamentals of Computation Theory
• On an NP-hard sorting problem
• Block sorting: a characterization and some heuristics
• Bounding prefix transposition distance for strings and permutations

This page was built for publication: Block Sorting is Hard

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