Minimum common string partition problem: hardness and approximations
From MaRDI portal
Publication:2571293
zbMath1102.68139MaRDI QIDQ2571293
Avraham Goldstein, Petr Kolman, Jie Zheng
Publication date: 1 November 2005
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/126825
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (13)
Solving the minimum common string partition problem with the help of ants ⋮ 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 ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ Quick Greedy Computation for Minimum Common String Partitions ⋮ On the kernelization complexity of string problems ⋮ Quick greedy computation for minimum common string partition ⋮ Bounding prefix transposition distance for strings and permutations ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ The complexity of string partitioning
This page was built for publication: Minimum common string partition problem: hardness and approximations