A W[2]-Hard Variant of Common Approximate Substring
| dc.contributor.author | Smith, Andrew, D. | |
| dc.date.accessioned | 2023-03-01T18:27:11Z | |
| dc.date.available | 2023-03-01T18:27:11Z | |
| dc.date.issued | 2002 | |
| dc.description.abstract | Given a set F of strings and two integers d < l, the common approximate substring problem asks whether there is a string C of length l, such that each member of F contains a substring that differs from C in at most d positions. For a fixed number of strings, and fixed alphabet size, Fellows et al. [2] showed this problem to be hard for the class W[1] of the W-hierarchy. We strengthen this result and show that the problem is W[2]-hard by a parameterized reduction from set cover. | |
| dc.description.copyright | Copyright @ Andrew D. Smith, 2002. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14708 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | A W[2]-Hard Variant of Common Approximate Substring | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1