Sorting permutations and binary strings by length-weighted rearrangements

DOI10.1016/J.TCS.2018.01.012MaRDI QIDQ683752zbMATH OpenOpenAlexFDO

Authors Carla Negri Lintzmayer, Guillaume Fertin, Zanoni Dias

Publication date 9 February 2018

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

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

zbMATH Keywords

approximation algorithmsdiameterreversalstranspositionsgenome rearrangementsprefix rearrangements

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Searching and sorting (68P10) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Length-weighted \(\lambda\)-rearrangement distance
• Approximation algorithms for sorting by length-weighted prefix and suffix operations
• Improved bounds on sorting by length-weighted reversals
• Improved bounds on sorting with length-weighted reversals
• Approximation algorithms for sorting permutations by fragmentation-weighted operations

Cites work

• scientific article; zbMATH DE number 1947393 (Why is no real title available?)
• Advances on sorting by reversals
• Algorithms for computational biology. First international conference, AlCoB 2014, Tarragona, Spain, July 1--3, 2014. Proceedings
• Algorithms – ESA 2005
• An (18/11)n upper bound for sorting by prefix reversals
• An approximation algorithm for sorting by reversals and transpositions
• Approximation algorithms for sorting by length-weighted prefix and suffix operations
• Bounding prefix transposition distance for strings and permutations
• Bounds for sorting by prefix reversal
• Combinatorial Pattern Matching
• Combinatorics of genome rearrangements.
• Edit Distances and Factorisations of Even Permutations
• Genome Rearrangements and Sorting by Reversals
• Improved bounds on sorting by length-weighted reversals
• Introduction to algorithms.
• On average and highest number of flips in pancake sorting
• On the Diameter of the Pancake Network
• On the problem of sorting burnt pancakes
• Prefix and Suffix Reversals on Strings
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting a bridge hand
• Sorting by prefix reversals and prefix transpositions
• Sorting permutations by prefix and suffix versions of reversals and transpositions
• Transforming cabbage into turnip

Cited in

(10)

• Weighted Minimum-Length Rearrangement Scenarios.
• scientific article; zbMATH DE number 5124574 (Why is no real title available?)
• Length-weighted \(\lambda\)-rearrangement distance
• Sorting circular binary strings with length weighted transpositions
• Indexing permutations for binary strings
• Improved bounds on sorting with length-weighted reversals
• Approximation algorithms for sorting permutations by length-weighted short rearrangements
• Sorting parity encodings by reusing variables
• Approximation algorithms for sorting by length-weighted prefix and suffix operations
• Improved bounds on sorting by length-weighted reversals

This page was built for publication: Sorting permutations and binary strings by length-weighted rearrangements

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