Charge and reduce
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , , |
| Format: | article |
| Published: |
2015
|
| Online Access: | http://hdl.handle.net/10725/2773 http://dx.doi.org/10.1016/j.disopt.2010.10.003 http://www.sciencedirect.com/science/article/pii/S1572528610000708 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 NP-complete 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 fixed-parameter 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). |
|---|