A new dynamic programming algorithm for the simplified partial digest problem

DOI10.1016/J.TCS.2023.113801MaRDI QIDQ2697542zbMATH OpenOpenAlexFDO

Authors Biing-Feng Wang

Publication date 12 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.113801

zbMATH Keywords

algorithmsbacktrackingdynamic programminggenome mappingrestriction sites analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A fast algorithm for the partial digest problem
• On the approximability of the simplified partial digest problem
• The simplified partial digest problem: approximation and a graph-theoretic model
• A lower bound on the number of solutions to the probed partial digest problem
• scientific article; zbMATH DE number 5154894
• A way to improve the key recovery accuracy based on dynamic programming
• A new practical algorithm for the construction of a perfect hash function
• A new NP-complete problem and public-key identification

Cites work

• A fast algorithm for the partial digest problem
• A partial digest approach to restriction site mapping
• Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 5154894 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 2209734 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Multiple solutions of DNA restriction mapping problems
• On the approximability of the simplified partial digest problem
• Some necessary clarifications about the chords' problem and the partial digest problem
• The simplified partial digest problem: approximation and a graph-theoretic model

Cited in

(1)

• Partial digest is hard to solve for erroneous input data

This page was built for publication: A new dynamic programming algorithm for the simplified partial digest problem

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