Permutation-constrained common string partitions with applications

DOI10.1007/S00453-024-01276-7MaRDI QIDQ6647775zbMATH OpenFDO

Authors Manuel Lafond, Binhai Zhu

Publication date 3 December 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-024-01276-7

zbMATH Keywords

FPTgenome rearrangementminimum common string partitionpermutation-constrained common string partition

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• APPROXIMATE BLOCK SORTING
• Combinatorics of genome rearrangements.
• Computing the tandem duplication distance is NP-hard
• Edit distance with block operations
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 7651113 (Why is no real title available?)
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Minimum common string partition problem: hardness and approximations
• Minimum common string partition revisited
• Permutation-constrained common string partitions with applications
• Sorting by multi-cut rearrangements
• Sorting permutations by block-interchanges
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting strings by reversals and by transpositions
• The complexity of finding common partitions of genomes with predefined block sizes
• The greedy algorithm for the minimum common string partition problem

This page was built for publication: Permutation-constrained common string partitions with applications

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