In this paper we address the minimum common string partition problem. We show that even a very restricted version of the problem is NP-hard and APX-hard, and we also describe several aproximation algorithms.
In this paper we address the minimum common string partition problem. We show that even a very restricted version of the problem is NP-hard and APX-hard, and we also describe several aproximation algorithms. (en)
V tomto článku studujeme problém minimálního společného dělení dvou řetězců. Dokážeme, že již velice omezená varianta problému je NP-těžká a APX-těžká, a také přinášíme několik aproximačních algoritmů. (cs)