The greedy algorithm for the minimum common string partition problem

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F04%3A00106921" target="_blank" >RIV/67985840:_____/04:00106921 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

The greedy algorithm for the minimum common string partition problem

Original language description

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.

Czech name

Hladový algoritmus pro minimální společné rozdělení řetízků

Czech description

Článek studuje hladový algoritmus pro minimální společné rozdělení řetízků.

Type

D - Article in proceedings

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2004

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the APPROX

ISBN

—

ISSN

—

e-ISSN

—

Number of pages

12

Pages from-to

84-95

Publisher name

Springer

Place of publication

Berlin

Event location

Cambridge

Event date

Aug 22, 2004

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—