期刊
THEORETICAL COMPUTER SCIENCE
卷 525, 期 -, 页码 30-41出版社
ELSEVIER
DOI: 10.1016/j.tcs.2013.05.006
关键词
Local search; Parameterized complexity; Parameterized intractability; Closest String; Longest Common Subsequence; Shortest Common Supersequence; Shortest Common Superstring
资金
- DFG excellence cluster MMCI
We address the problem of whether the brute-force procedure for the local improvement step in a local search algorithm can substantially be improved when applied to classical NP-hard string problems. We examine four of the more prominent problems in this domain: CLOSEST STRING, LONGEST COMMON SUBSEQUENCE, SHORTEST COMMON SUPERSEQUENCE, and SHORTEST COMMON SUPERSTRING. Herein, we consider arguably the most fundamental string distance measure, namely the Hamming distance, which has been applied in practical local search implementations for string problems. Our results indicate that for all four problems, the brute-force algorithm cannot be considerably improved. (C) 2013 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据