Approximation algorithms for sorting permutations by extreme block-interchanges

DOI10.1016/J.TCS.2021.08.031OpenAlexW3196558038MaRDI QIDQ2235751FDOQ2235751

Bhadrachalam Chitturi, Jayakumar Pai

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)

Cites Work

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

Cited In (6)

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

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)