The greedy algorithm for the minimum common string partition problem

0041403 - MÚ 2007 RIV US eng J - Journal Article
Chrobak, M. - Kolman, P. - Sgall, Jiří
The greedy algorithm for the minimum common string partition problem.
[Hladový algoritmus pro minimální společné rozdělení řetízků.]
ACM Transactions on Algorithms. Roč. 1, č. 2 (2005), s. 350-366. ISSN 1549-6325. E-ISSN 1549-6333
R&D Projects: GA MŠMT(CZ) 1M0545; GA ČR(CZ) GA201/05/0124; GA AV ČR(CZ) IAA1019401
Institutional research plan: CEZ:AV0Z10190503
Keywords : string algorithms * approximation algorithms
Subject RIV: BA - General Mathematics

In the Minimum Common String Partition problem(MCSP) we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings in the partition. Even a special case, denoted 2-MCSP, where each letter occurs at most twice in each input string, is NP-hard. We study a greedy algorithm for MCSP that at each step extracts a longest common substring from the given strings.

Článek analyzuje hladový algoritmus pro minimální společné rozdělení řetízků.
Permanent Link: http://hdl.handle.net/11104/0134878