.png){kind=icon}
.png){kind=icon}
Return
String Consensus Problems with Swaps and Substitutions
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-05228-5_12.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
String consensus problems aim at finding a string that minimizes some given distance with respect to an input set of strings. In particular, in the Closest String problem, we are given a set of strings of equal length and a radius dd. The goal is to find a new string that differs from each input string by at most dd substitutions. We study a generalization of this problem where, in addition to substitutions, swaps of adjacent characters are also permitted, each operation incurring a unit cost. Amir et al. showed that this generalized problem is NP-hard, even when only swaps are allowed. In this paper, we show that it is FPT with respect to the parameter dd. Moreover, we investigate a variant in which the goal is to minimize the sum of distances from the output string to all input strings. For this version, we present a polynomial-time algorithm.
Keywords:
Closest String
Parameterized Algorithms
Swap Distances
String Consensus
Journal
S
IF:
0
Papers:
22
Citations:
0
Organization
View more organizations