A Fixed-Parameter Algorithm for String-to-String Correction

Abu-Khzam, F. N., Fernau, H., Langston, M. A., Lee-Cultura, S. and Stege, U.

    In the String-to-String Correction problem we are given two strings x and y and a positive integer k, and are asked whether it is possible to transform y into x with at most k single character deletions and adjacent character exchanges. We present a first simple fixed-parameter algorithm for String- to-String Correction that runs in O∗(2^k). Moreover, we present a search tree algorithm that exhibits a novel technique of bookkeeping called charging, which leads to an improved algorithm whose running time is in O∗(1.62^k).
Cite as: Abu-Khzam, F. N., Fernau, H., Langston, M. A., Lee-Cultura, S. and Stege, U. (2010). A Fixed-Parameter Algorithm for String-to-String Correction. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 31-38
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS