2012 | OriginalPaper | Buchkapitel
Restricted and Swap Common Superstring: A Parameterized View
verfasst von : Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In several areas, in particular in bioinformatics and in AI planning, Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied. In this paper we consider two variants of SCS recently introduced (Restricted Common Superstring,
$\ensuremath{\text{\textsc{RCS}}}$
) and (Swapped Common Superstring,
$\ensuremath{\text{\textsc{SWCS}}}$
). In
$\ensuremath{\text{\textsc{RCS}}}$
we are given a set
S
of strings and a multiset, and we look for an ordering
$\mathcal{M}_o$
of
$\mathcal{M}$
such that the number of input strings which are substrings of
$\mathcal{M}_o$
is maximized. In
$\ensuremath{\text{\textsc{SWCS}}}$
we are given a set
S
of strings and a text
$\mathcal{T}$
, and we look for a swap ordering
$\mathcal{T}_o$
of
$\mathcal{T}$
(an ordering of
$\mathcal{T}$
obtained by swapping only some pairs of adjacent characters) such that the number of input strings which are substrings of
$\mathcal{T}_o$
is maximized. In this paper we investigate the parameterized complexity of the two problems. We give two fixed-parameter algorithms, where the parameter is the size of the solution, for
$\ensuremath{\text{\textsc{SWCS}}}$
and
$\ensuremath{\text{\textsc{$\ell$-RCS}}} $
(the
$\ensuremath{\text{\textsc{RCS}}}$
problem restricted to strings of length bounded by a parameter ℓ). Furthermore, we complement these results by showing that
$\ensuremath{\text{\textsc{SWCS}}}$
and
$\ensuremath{\text{\textsc{$\ell$-RCS}}} $
do not admit a polynomial kernel.