The greedy algorithm for the minimum common string partition problem

0041403 - MÚ 2007 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA MŠMT(CZ) 1M0545; GA ČR(CZ) GA201/05/0124; GA AV ČR(CZ) IAA1019401
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: string algorithms * approximation algorithms
Kód oboru RIV: BA - Obecná matematika

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ů.
Trvalý link: http://hdl.handle.net/11104/0134878