The greedy algorithm for the minimum common string partition problem

0106921 - MU-W 20040128 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Sgall, Jiří - Kolman, P. - Chrobak, M.
The greedy algorithm for the minimum common string partition problem.
[Hladový algoritmus pro minimální společné rozdělení řetízků.]
Proceedings of the APPROX. Berlin: Springer, 2004, s. 84-95.
[Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/7./, APPROX 2004, and International Workshop on Randomization and Computation/8./, RANDOM 2004. Cambridge (US), 22.08.2004-24.08.2004]
Grant CEP: GA MŠMT LN00A056; GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z1019905
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 greed algorithm for MCSP.

Článek studuje hladový algoritmus pro minimální společné rozdělení řetízků.
Trvalý link: http://hdl.handle.net/11104/0014093