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].
Parameterized tractability of the maximum-duo preservation string mapping problem
BERETTA, STEFANO
Primo
;CASTELLI, MAUROSecondo
;
2016
Abstract
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).
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
MaxDuo.pdf
accesso aperto
Descrizione: Post-print
Dimensione
324.34 kB
Formato
Adobe PDF
|
324.34 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
