Parameterized lower bound and inapproximability of polylogarithmic string barcoding

DOI10.1007/S10878-007-9097-XMaRDI QIDQ941834zbMATH OpenOpenAlexFDO

Authors Chunmei Liu, Yinglei Song, Legand L. Burge

Publication date 2 September 2008

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-007-9097-x

Mathematics Subject Classification ID

Applications of graph theory (05C90) Complexity and performance of numerical algorithms (65Y20) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40)

Recommendations

• Faster Algorithm for the Set Variant of the String Barcoding Problem
• Distinguishing string selection problems.
• Parameterized complexity analysis for the closest string with wildcards problem
• scientific article; zbMATH DE number 2086391
• Parameterized intractability of distinguishing substring selection

Cites work

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Computational Science – ICCS 2005
• Efficient algorithms for finding maximum matching in graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• The importance of being biased
• Tight approximability results for test set problems in bioinformatics

Cited in

(3)

• scientific article; zbMATH DE number 5289787 (Why is no real title available?)
• Faster Algorithm for the Set Variant of the String Barcoding Problem
• Computational Science – ICCS 2005

This page was built for publication: Parameterized lower bound and inapproximability of polylogarithmic string barcoding

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