Can I read On the Complexity of Finding Common Approximate Substrings on EtoBox?

On the Complexity of Finding Common Approximate Substrings by Patricia A. Evans; Andrew D. Smith; H.Todd Wareham is a Computer Science article available to read on EtoBox.

What is On the Complexity of Finding Common Approximate Substrings about?

Problems associated with ÿnding strings that are within a speciÿed Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBSTRING (CAS) problem. Our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. In order to achieve ÿxed-parameter tractability, either a ÿxed string length or both a ÿxed size alphabet and ÿxed substring length are su cient. Fixing either the string length or the alphabet size and Hamming distance is shown to be necessary, unless W [1] = FPT . An assortment of parameterized class membership and hardness results cover all other parameterized variants, showing in particular the e ect of ÿxing the number of strings.

Who reads On the Complexity of Finding Common Approximate Substrings?

Author

Patricia A. Evans; Andrew D. Smith; H.Todd Wareham

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2003

Language

EN

Field

Computer Science (Physical Sciences)