scientific article; zbMATH DE number 2086391

MaRDI QIDQ4736845zbMATH OpenFDO

Authors Michael R. Fellows, Jens Gramm, Rolf Niedermeier

Publication date 11 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2285/22850262.htm

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the parameterized intractability of motif search problems
• Closest Substring Problems with Small Distances
• Hard problems in similarity searching
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• The parameterized complexity of sequence alignment and consensus

Cited in

(16)

• An improved lower bound on approximation algorithms for the closest substring problem
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Multivariate algorithmics for NP-hard string problems
• On the parameterized intractability of motif search problems
• Hard problems in similarity searching
• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• The parameterized complexity of the shared center problem
• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• Parameterized intractability of distinguishing substring selection
• Parameterized complexity analysis for the closest string with wildcards problem
• Closest Substring Problems with Small Distances
• Separating sets of strings by finding matching patterns is almost always hard
• The parameterized complexity of the shared center problem
• Parameterized lower bound and inapproximability of polylogarithmic string barcoding
• The invariant problem for binary string structures and the parallel complexity theory of queries
• On the complexity of finding common approximate substrings.

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4736845)