This is a corrigendum for our paper [1], as we have found that the first FPT algorithm for the Maximum-Duo Preservation String Mapping Problem we presented is incorrect. However, we show that, by slightly modifying the color-coding technique on which the algorithm is based, we can fix the error, thus giving a correct FPT algorithm for Maximum-Duo Preservation String Mapping Problem.

Beretta, S., Castelli, M., Dondi, R. (2016). Erratum: Corrigendum to “Parameterized tractability of the maximum-duo preservation string mapping problem” (Theoretical Computer Science (2016) 646 (16–25) (S0304397516303255) (10.1016/j.tcs.2016.07.011)). THEORETICAL COMPUTER SCIENCE, 653, 108-110 [10.1016/j.tcs.2016.09.015].

Erratum: Corrigendum to “Parameterized tractability of the maximum-duo preservation string mapping problem” (Theoretical Computer Science (2016) 646 (16–25) (S0304397516303255) (10.1016/j.tcs.2016.07.011))

BERETTA, STEFANO
Primo
;
CASTELLI, MAURO
Secondo
;
2016

Abstract

This is a corrigendum for our paper [1], as we have found that the first FPT algorithm for the Maximum-Duo Preservation String Mapping Problem we presented is incorrect. However, we show that, by slightly modifying the color-coding technique on which the algorithm is based, we can fix the error, thus giving a correct FPT algorithm for Maximum-Duo Preservation String Mapping Problem.
Articolo in rivista - Articolo scientifico
Common string partition; Computational biology; Parameterized algorithms;
Common string partition; Computational biology; Parameterized algorithms; Theoretical Computer Science; Computer Science (all)
English
2016
653
108
110
open
Beretta, S., Castelli, M., Dondi, R. (2016). Erratum: Corrigendum to “Parameterized tractability of the maximum-duo preservation string mapping problem” (Theoretical Computer Science (2016) 646 (16–25) (S0304397516303255) (10.1016/j.tcs.2016.07.011)). THEORETICAL COMPUTER SCIENCE, 653, 108-110 [10.1016/j.tcs.2016.09.015].
File in questo prodotto:
File Dimensione Formato  
CorrigendumMaxDuo.pdf

accesso aperto

Descrizione: Post-print
Dimensione 193.27 kB
Formato Adobe PDF
193.27 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/174094
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
Social impact