Complexity of approximating closest substring problems.

DOI10.1007/B11926MaRDI QIDQ5900798zbMATH OpenOpenAlexFDO

Authors Patricia A. Evans, Andrew D. Smith

Publication date 20 April 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b11926

zbMATH Keywords

approximation algorithmsclosest substringhardness of approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Algorithms on strings (68W32) Computational methods for problems pertaining to biology (92-08)

Recommendations

• scientific article; zbMATH DE number 1615273
• On the closest string and substring problems
• More efficient algorithms for closest string and substring problems
• A Lower Bound on Approximation Algorithms for the Closest Substring Problem
• An improved lower bound on approximation algorithms for the closest substring problem

Cited in

(15)

• Alphabet indexing for approximating features of symbols
• On the complexity of finding common approximate substrings.
• Complexity of substring search in a set of strings
• Hard problems in similarity searching
• Randomized fixed-parameter algorithms for the closest string problem
• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• On the closest string and substring problems
• A Lower Bound on Approximation Algorithms for the Closest Substring Problem
• A three-string approach to the closest string problem
• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• Subsequence Packing: Complexity, Approximation, and Application
• The Minimum Substring Cover Problem
• Fundamentals of Computation Theory
• The minimum substring cover problem
• An improved lower bound on approximation algorithms for the closest substring problem

This page was built for publication: Complexity of approximating closest substring problems.

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