Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable

DOI10.1137/1.9781611973402.8zbMath1421.68253arXiv1305.0649OpenAlexW2951751137MaRDI QIDQ5383967

Laurent Bulteau, Christian Komusiewicz

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.0649

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Genetics and epigenetics (92D10) Algorithms on strings (68W32)

Related Items (12)

Sorting by multi-cut rearrangements ⋮ Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ Permutation-constrained common string partitions with applications ⋮ The complexity of finding common partitions of genomes with predefined block sizes ⋮ Unnamed Item ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ Fixed-parameter tractability for the Tree Assembly problem ⋮ Quick greedy computation for minimum common string partition ⋮ A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem ⋮ Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition ⋮ Unnamed Item ⋮ A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

This page was built for publication: Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable