Approximation algorithms for sorting permutations by extreme block-interchanges

DOI10.1016/J.TCS.2021.08.031MaRDI QIDQ2235751zbMATH OpenOpenAlexFDO

Authors Jayakumar Pai, Bhadrachalam Chitturi

Publication date 21 October 2021

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

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

zbMATH Keywords

approximation algorithmsblock-interchangepermutation cycle graphprefix block-interchange

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Sorting permutations by block-interchanges
• Sorting by short block-moves
• APPROXIMATE BLOCK SORTING
• An improved block-interchange algorithm
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves

Cites work

• A group-theoretic model for symmetric interconnection networks
• A new upper bound for sorting permutations with prefix transpositions
• A note on complexity of genetic mutations
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The average number of block interchanges needed to sort a permutation and a recent result of Stanley
• The complexity of finding minimum-length generator sequences
• The minimum-length generator sequence problem is NP-hard
• Tighter upper bound for sorting permutations with prefix transpositions

Cited in

(8)

• Approximation algorithms for sorting permutations by fragmentation-weighted operations
• An improved algorithm for sorting by block-interchanges based on permutation groups
• A quadratic time 2-approximation algorithm for block sorting
• An improved block-interchange algorithm
• Sorting by prefix block-interchanges
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Block Sorting Is APX-Hard
• Approximation algorithms for sorting permutations by length-weighted short rearrangements

This page was built for publication: Approximation algorithms for sorting permutations by extreme block-interchanges

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