Listing Center Strings Under the Edit Distance Metric
Listing Center Strings Under the Edit Distance Metric
复制标题
DOI：
10.1007/978-3-319-26626-8_57
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Hiromitsu Maji;Taisuke Izumi
中科院分区：
文献类型：
--
作者：
Hiromitsu Maji;Taisuke Izumi
给定字母表上长度为k的字符串的集合W，W的中心字符串被定义为W中所有字符串的最大距离t0在某个特定度量下最小的字符串W。我们提出了一个新的算法，这个问题的决策版本下的编辑距离度量。给定一个阈值参数d，该算法列出所有字符串，使得与任何输入字符串的距离以dintime为界，其中M是输出字符串的数量。据我们所知，这是第一个在编辑距离度量下的中心字符串FPT算法（甚至作为查找算法）。通过稍加修改，我们还得到了一个列W的长度为l的公共序列的算法，该算法是在时间上运行的。
Given a setWofkstrings of lengthnover an alphabet, the center string ofWis defined as the stringwsuch that the maximum distance towof all strings inWis minimized under some specified metric. We present a new algorithm for the decision version of this problem under the edit distance metric. Given a threshold parameterd, the algorithm lists all the strings such that the distance from any input string is bounded bydintime, whereMis the number of the output strings. To the best of our knowledge, this is the first FPT algorithm for the center string under the edit distance metric (even as a finding algorithm). By a slight modification, we also obtain an algorithm listing length-lcommon subsequences ofW, which runs intime.