In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O(k6).
Beretta, S., Castelli, M., & Dondi, R. (2016). Parameterized tractability of the maximum-duo preservation string mapping problem. THEORETICAL COMPUTER SCIENCE, 646, 16-25 [10.1016/j.tcs.2016.07.011].
Citazione: | Beretta, S., Castelli, M., & Dondi, R. (2016). Parameterized tractability of the maximum-duo preservation string mapping problem. THEORETICAL COMPUTER SCIENCE, 646, 16-25 [10.1016/j.tcs.2016.07.011]. | |
Tipo: | Articolo in rivista - Articolo scientifico | |
Carattere della pubblicazione: | Scientifica | |
Presenza di un coautore afferente ad Istituzioni straniere: | Si | |
Titolo: | Parameterized tractability of the maximum-duo preservation string mapping problem | |
Autori: | Beretta, S; Castelli, M; Dondi, R | |
Autori: | CASTELLI, MAURO (Secondo) | |
Data di pubblicazione: | 2016 | |
Lingua: | English | |
Rivista: | THEORETICAL COMPUTER SCIENCE | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.tcs.2016.07.011 | |
Appare nelle tipologie: | 01 - Articolo su rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
MaxDuo.pdf | Post-print | N/A | Open Access Visualizza/Apri |