DNA models and algorithms for NP-complete problems

DOI10.1006/JCSS.1998.1586MaRDI QIDQ1276167zbMATH OpenOpenAlexFDO

Authors Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay

Publication date 17 January 1999

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1998.1586

zbMATH Keywords

DNA computing

Mathematics Subject Classification ID

Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Is DNA computing viable for 3-SAT problems?
• scientific article; zbMATH DE number 1156876
• On the power of DNA-computing
• New algorithms for some NP-optimization problems by DNA computing
• On the computational power of DNA

Cites work

• scientific article; zbMATH DE number 434654 (Why is no real title available?)
• scientific article; zbMATH DE number 53571 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• scientific article; zbMATH DE number 1306877 (Why is no real title available?)
• scientific article; zbMATH DE number 515744 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Parallel concepts in graph theory
• Probability with Martingales
• Sum of the reciprocals of the binomial coefficients

Cited in

(27)

• Complexity analysis of the SAT engine: DNA algorithms as probabilistic algorithms.
• Genetic algorithm in DNA computing: a solution to the maximal clique problem
• DNA and quantum based algorithms for VLSI circuits testing
• Is DNA computing viable for 3-SAT problems?
• scientific article; zbMATH DE number 2013796 (Why is no real title available?)
• scientific article; zbMATH DE number 2089972 (Why is no real title available?)
• On the computational power of DNA
• Molecular computing, bounded nondeterminism, and efficient recursion
• Genetic code-based DNA computation for the Hamiltonian path problem
• New algorithms for some NP-optimization problems by DNA computing
• A ``DNA origami-based approach to the solution of graph coloring problem
• A concurrent multi-string matching from multi-text algorithm based on the algorithm of Hamiltonian Path Problem and DNA computation
• On the scalability of biocomputing algorithms: the case of the maximum clique problem
• A molecular beacon computing model of maximum matching problem
• scientific article; zbMATH DE number 2040825 (Why is no real title available?)
• Solving the minimum bisection problem using a biologically inspired computational model
• Spatial cluster analysis by the Adleman-Lipton DNA computing model and flexible grids
• scientific article; zbMATH DE number 1351098 (Why is no real title available?)
• scientific article; zbMATH DE number 5630435 (Why is no real title available?)
• Molecular solution to the optimal linear arrangement problem based on DNA computation
• Solving the maximal matching problem with DNA molecules in Adleman-Lipton model
• Efficient DNA sticker algorithms for NP-complete graph problems
• Solving two-dimensional cutting stock problem via a DNA computing algorithm
• scientific article; zbMATH DE number 5510507 (Why is no real title available?)
• DNA2DNA computations: A potential “killer app”?
• scientific article; zbMATH DE number 426425 (Why is no real title available?)
• scientific article; zbMATH DE number 1418472 (Why is no real title available?)

This page was built for publication: DNA models and algorithms for NP-complete problems

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