Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 41-49 |
| Number of pages | 9 |
| Journal | Discrete Optimization |
| Volume | 8 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2011 |
| Externally published | Yes |
Fingerprint
Cite this
}
Charge and reduce : A fixed-parameter algorithm for String-to-String Correction. / Abu Khzam, Faisal; Fernau, Henning; Langston, M; Lee-Cultura, S; Stege, Ulrike.
In: Discrete Optimization, Vol. 8, No. 1, 2011, p. 41-49.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - Charge and reduce
T2 - A fixed-parameter algorithm for String-to-String Correction
AU - Abu Khzam, Faisal
AU - Fernau, Henning
AU - Langston, M
AU - Lee-Cultura, S
AU - Stege, Ulrike
PY - 2011
Y1 - 2011
N2 - String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NPcomplete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixedparameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.6181kn).
AB - String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NPcomplete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixedparameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.6181kn).
U2 - 10.1016/j.disopt.2010.10.003
DO - 10.1016/j.disopt.2010.10.003
M3 - Article
VL - 8
SP - 41
EP - 49
JO - Discrete Optimization
JF - Discrete Optimization
SN - 1572-5286
IS - 1
ER -