Back to search

University of Victoria (Canada)

String to String Correction Kernelization

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Watt, Nathaniel
Advisors dc:contributor.supervisor
  • Stege, Ulrike
  • Ganti, Sudhakar

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/4866

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Watt, Nathaniel. String to String Correction Kernelization. Master of Science M.Sc. thesis, 2013. http://hdl.handle.net/1828/4866