On approximate parameterized string matching and related problems
| dc.contributor.author | Das, Shibsankar | |
| dc.date.accessioned | 2016-08-31T07:25:20Z | |
| dc.date.accessioned | 2023-10-20T12:30:41Z | |
| dc.date.available | 2016-08-31T07:25:20Z | |
| dc.date.available | 2023-10-20T12:30:41Z | |
| dc.date.issued | 2016 | |
| dc.description | Supervisor: Kalpesh Kapoor | en_US |
| dc.description.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. | en_US |
| dc.identifier.other | ROLL NO.10612301 | |
| dc.identifier.uri | https://gyan.iitg.ac.in/handle/123456789/734 | |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TH-1507; | |
| dc.subject | MATHEMATICS | en_US |
| dc.title | On approximate parameterized string matching and related problems | en_US |
| dc.type | Thesis | en_US |
Files
License bundle
1 - 1 of 1