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).
Parameterized tractability of the maximum-duo preservation string mapping problem
DONDI, Riccardo
2016-01-01
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 allegato/i alla scheda:
| File | Dimensione del file | Formato | |
|---|---|---|---|
|
MaxDuo.pdf
accesso aperto
Versione:
Documento in Pre-print
Licenza:
Licenza default Aisberg
Dimensione del file
324.34 kB
Formato
Adobe PDF
|
324.34 kB | Adobe PDF | Visualizza/Apri |
|
Dondi_2016_Theoreticalcomputerscience_Maximum-duopreservation.pdf
Solo gestori di archivio
Versione:
publisher's version - versione editoriale
Licenza:
Licenza default Aisberg
Dimensione del file
403.97 kB
Formato
Adobe PDF
|
403.97 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo
