Počet záznamů: 1
The greedy algorithm for the minimum common string partition problem
- 1.
SYSNO ASEP 0041403 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Ostatní články Název The greedy algorithm for the minimum common string partition problem Překlad názvu Hladový algoritmus pro minimální společné rozdělení řetízků Tvůrce(i) Chrobak, M. (US)
Kolman, P. (CZ)
Sgall, Jiří (MU-W) RID, ORCID, SAIZdroj.dok. ACM Transactions on Algorithms - ISSN 1549-6325
Roč. 1, č. 2 (2005), s. 350-366Poč.str. 17 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova string algorithms ; approximation algorithms Vědní obor RIV BA - Obecná matematika CEP 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy GA201/05/0124 GA ČR - Grantová agentura ČR IAA1019401 GA AV ČR - Akademie věd CEZ AV0Z10190503 - MU-W (2005-2011) Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2007
Počet záznamů: 1