.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
字符串一致性问题旨在寻找一个字符串，使其相对于输入字符串集合的给定距离最小化。具体而言，在最近字符串问题中，给定一组等长字符串和一个半径dd。目标是找到一个新字符串，使其与每个输入字符串的差异最多为dd次替换。我们研究了该问题的一个推广，其中除了替换外，还允许相邻字符的交换，每次操作均产生单位成本。Amir等人证明了，即使仅允许交换操作，该推广问题也是NP难的。在本文中，我们证明该问题关于参数dd是固定参数可解的。此外，我们研究了一个变体，其中目标是最小化输出字符串到所有输入字符串的距离之和。对于此版本，我们提出了一种多项式时间算法。
Keyword:
Closest String
Parameterized Algorithms
Swap Distances
String Consensus
期刊
S
IF:
0
论文数:
22
被引数:
0
查看更多机构
.png){kind=icon}
