Approximation algorithms for sorting by bounded singleton moves

DOI10.1016/J.TCS.2022.03.011MaRDI QIDQ2143142zbMATH OpenOpenAlexFDO

Authors Shengjun Xie, Haodi Feng, Haitao Jiang, Daming Zhu

Publication date 31 May 2022

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

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

zbMATH Keywords

approximation algorithmbounded singleton movepermutation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

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

Cites work

• A 14/11-approximation algorithm for sorting by short block-moves
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• scientific article; zbMATH DE number 194916 (Why is no real title available?)
• On sorting by 3-bounded transpositions
• Sorting a bridge hand
• Sorting by bounded block-moves
• Sorting by short block-moves
• Sorting by Transpositions

Cited in

(1)

• An approximation algorithm for sorting by bounded singleton moves

This page was built for publication: Approximation algorithms for sorting by bounded singleton moves

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