Sorting by short block-moves

DOI10.1007/S004530010041MaRDI QIDQ1587783zbMATH OpenOpenAlexFDO

Authors Lenwood S. Heath, John Paul C. Vergara

Publication date 3 December 2000

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004530010041

zbMATH Keywords

sorting permutations

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• A (1+)-approximation algorithm for sorting by short block-moves
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• A 14/11-approximation algorithm for sorting by short block-moves
• APPROXIMATE BLOCK SORTING
• Sorting permutations by block-interchanges

Cited in

(21)

• A quadratic time 2-approximation algorithm for block sorting
• Sorting by bounded block-moves
• Sorting a permutation by best short swaps
• Approximation algorithms for sorting by bounded singleton moves
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Short proofs for cut-and-paste sorting of permutations
• On sorting by 3-bounded transpositions
• Representing permutations with few moves
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• On Sorting by 3-Bounded Transpositions
• A (1+)-approximation algorithm for sorting by short block-moves
• Computing and Combinatorics
• APPROXIMATE BLOCK SORTING
• A 14/11-approximation algorithm for sorting by short block-moves
• Block Sorting is Hard
• Sorting a bridge hand
• Sorting by prefix block-interchanges
• scientific article; zbMATH DE number 7765413 (Why is no real title available?)
• Short block-move-CPP is \textsf{NP}-complete
• On the complexity of the median and closest permutation problems
• A review of metrics on permutations for search landscape analysis

This page was built for publication: Sorting by short block-moves

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