The greedy algorithm for the minimum common string partition problem

DOI10.1145/1103963.1103971zbMath1321.68550OpenAlexW1977957904MaRDI QIDQ2944502

Jiří Sgall, Petr Kolman, Marek Chrobak

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1103963.1103971

zbMATH Keywords

approximation algorithmsstring algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (11)

Solving the minimum common string partition problem with the help of ants ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ 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 ⋮ Approximating reversal distance for strings with bounded number of duplicates ⋮ Unnamed Item ⋮ Fixed-parameter tractability for the Tree Assembly problem ⋮ Quick Greedy Computation for Minimum Common String Partitions ⋮ Efficient algorithms for the block edit problems ⋮ Quick greedy computation for minimum common string partition

This page was built for publication: The greedy algorithm for the minimum common string partition problem