The StringToStringCorrection problem asks, given mutable string M, target string T, and positive integer k, can M be mutated into T using at most k operations (single symbol deletions or swaps of adjacent symbols) applied to M? The problem is known to be NP-complete. Abu-Khzam et al. give the first fixed-parameter algorithm for the problem when the parameter is the number of operations permitted. Their technique, charge and reduce, gives a O^∗(1.612k) bounded search tree algorithm, but leaves open whether a poly-size kernel exists. We show, using two polynomial time reduction rules on large regions of the input strings, that the problem has a problem kernel of size O(k^4). Our algorithm achieves this in a polynomial running time. Additionally, we introduce the problem k-MultiStringToStringCorrection (k-MS2SC), a generalized version of StringToStringCorrection, and prove it to be fixed-parameter tractable. / Graduate / 0984 / nwatt@uvic.ca
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/4866 |
| Date | 29 August 2013 |
| Creators | Watt, Nathaniel |
| Contributors | Stege, Ulrike, Ganti, Sudhakar |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.002 seconds