Parameterized tractability of the maximum-duo preservation string mapping problem

Stefano Beretta, Mauro Castelli, Riccardo Dondi

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

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).

Original languageEnglish
Pages (from-to)16-25
Number of pages10
JournalTheoretical Computer Science
Volume646
DOIs
Publication statusPublished - 2016

Keywords

  • Common string partition
  • Computational biology
  • Kernelization
  • Parameterized algorithms

Fingerprint

Dive into the research topics of 'Parameterized tractability of the maximum-duo preservation string mapping problem'. Together they form a unique fingerprint.

Cite this