Minimum common string partition problem: hardness and approximations

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

zbMATH Keywords

String comparison

Mathematics Subject Classification ID

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