Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Enumerating Neighbour and Closest Strings
verfasst von : Naomi Nishimura, Narges Simjour
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
We present the first parameterized enumeration algorithm for the
neighbour string problem
, where a neighbour string of
n
input strings, each of length ℓ, is a string that differs from input
s
i
in no more than
d
i
positions. The problem is NP-complete even when the
d
i
’s are equal; this is the well-known
closest string problem
.
Our new approach gives us the ability to tune the running time to optimize the algorithm for varying relative values of
n
and
d
= max
i
d
i
. For strings over an alphabet Σ, we can choose a tuning constant
λ
to obtain an algorithm that runs in time
O
(
n
ℓ + (
n
d
)
f
(
λ
)
(|Σ| − 1)
d
5
(1 +
λ
)
d
), where
f
is a function that decreases with increasing
λ
. When Σ = {0,1}, the dependency on
d
is an asymptotic improvement over the previous best parameterized time bound of
O
(
n
ℓ +
n
d
3
6.7308
d
) for finding a single solution.