Short block-move-CPP is \textsf{NP}-complete

DOI10.21711/231766362017/RMC4515MaRDI QIDQ6489485FDOQ6489485

Authors: Luís Felipe Ignácio Cunha, Vinícius F. dos Santos, L. A. B. Kowada, Celina M. H. de Figueiredo 

Publication date: 22 April 2024

Published in: Matemática Contemporânea (Search for Journal in Brave)

Recommendations

• On the computational complexity of closest genome problems
• Block sorting: a characterization and some heuristics
• APPROXIMATE BLOCK SORTING
• Sorting by short block-moves
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves

zbMATH Keywords

Hamming distance\textsf{NP}-completenessclosest problemshort block move

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Short block-move-CPP is \textsf{NP}-complete

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