The greedy algorithm for the minimum common string partition problem

0106921 - MU-W 20040128 RIV DE eng C - Conference Paper (international conference)
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]
R&D Projects: GA MŠMT LN00A056; GA AV ČR IAA1019401
Institutional research plan: CEZ:AV0Z1019905
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 greed algorithm for MCSP.

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