Permutation-constrained common string partitions with applications

DOI10.1007/s00453-024-01276-7MaRDI QIDQ6647775

Manuel Lafond, Binhai Zhu

Publication date: 3 December 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

genome rearrangementminimum common string partitionFPTpermutation-constrained common string partition

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum common string partition revisited
• Exact and approximation algorithms for the complementary maximal strip recovery problem
• Sorting permutations by block-interchanges
• Sorting by multi-cut rearrangements
• Permutation-constrained common string partitions with applications
• The complexity of finding common partitions of genomes with predefined block sizes
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• 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