Approximation algorithms for sorting permutations by extreme block-interchanges
From MaRDI portal
Publication:2235751
DOI10.1016/J.TCS.2021.08.031OpenAlexW3196558038MaRDI QIDQ2235751FDOQ2235751
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
Recommendations
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 (8)
- An improved block-interchange algorithm
- Sorting by prefix block-interchanges
- Approximation algorithms for sorting permutations by fragmentation-weighted operations
- A quadratic time 2-approximation algorithm for block sorting
- An improved algorithm for sorting by block-interchanges based on permutation groups
- 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)
