Permutation-constrained common string partitions with applications

DOI10.1007/978-3-030-86692-1_5OpenAlexW3204856573MaRDI QIDQ2146123

Manuel Lafond, Binhai Zhu

Publication date: 15 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-86692-1_5

zbMATH Keywords

genome rearrangementminimum common string partitionFPTpermutation-constrained common string partition

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (1)

The complexity of finding common partitions of genomes with predefined block sizes

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum common string partition revisited
• Sorting permutations by block-interchanges
• Sorting by multi-cut rearrangements
• Minimum common string partition problem: hardness and approximations
• Sorting Strings by Reversals and by Transpositions
• The greedy algorithm for the minimum common string partition problem
• Sorting by Transpositions Is Difficult
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Computing the Tandem Duplication Distance is NP-Hard
• APPROXIMATE BLOCK SORTING
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable

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