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

DOI10.21711/231766362017/RMC4515MaRDI QIDQ6489485zbMATH OpenFDO

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)

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)

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

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)