On approximate parameterized string matching and related problems
No Thumbnail Available
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis investigates problems concerned with Approximate Parameterized String Matching (APSM) under Hamming distance error model and related problems in graph theory. We introduce a term called error class in APSM problem and explore various combinatorial properties of the error classes. We also provide a tight lower bound on the weights of Maximum Weight Bipartite Matching (MWBM) of graphs which is correlated with the counting of number of error classes in APSM problem. The problem of APSM for a pair of equal length strings under Hamming distance is computationally equivalent to MWBM problem in graph theory. Let G (V, E, Wt) be an undirected, weighted bipartite graph where V be the vertex set and E be the edge set of G with positive integer weights on the edges which are given by the weight function Wt: E N. We fine-tune the existing decomposition theorem, originally proposed by Kao et al., for computing a MWBM of G.
Description
Supervisor: Kalpesh Kapoor
Keywords
MATHEMATICS