Efficient DNA sticker algorithms for NP-complete graph problems

DOI10.1016/S0010-4655(02)00270-9MaRDI QIDQ1605127zbMATH OpenFDO

Authors Karl-Heinz Zimmermann

Publication date 11 July 2002

Published in Computer Physics Communications (Search for Journal in Brave)

zbMATH Keywords

DNA algorithmbiomolecular computingHamiltonian directed path problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• On applying molecular computation to binary linear codes
• A sticker model-based DNA algorithm of maximum clique problem
• Sticker DNA computer model. II: Application
• Using sticker to solve the 3-dimensional matching problem in molecular supercomputers
• DNA models and algorithms for NP-complete problems

Cites work

• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 1241360 (Why is no real title available?)
• scientific article; zbMATH DE number 1241370 (Why is no real title available?)
• DNA computing, sticker systems, and universality
• DNA computing: Arrival of biological mathematics
• Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors

Cited in

(17)

• A batch separation experiment-based DNA algorithm of the maximum independent set problem
• scientific article; zbMATH DE number 2087503 (Why is no real title available?)
• Making all spanning tree problem based on sticker model
• A CONSTANT TIME ALGORITHM FOR DNA ADD
• A sticker model-based DNA algorithm of maximum clique problem
• On the scalability of biocomputing algorithms: the case of the maximum clique problem
• scientific article; zbMATH DE number 1953216 (Why is no real title available?)
• Aspects of Molecular Computing
• A new DNA algorithm to solve graph coloring problem
• Molecular solution to the optimal linear arrangement problem based on DNA computation
• A note on molecular computing algorithms for finding the shortest path with forbidden pairs
• Solving traveling salesman problem in the Adleman-Lipton model
• A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers
• On applying molecular computation to binary linear codes
• DNA algorithm for solution to Hamilton cycle problem
• Solving two-dimensional cutting stock problem via a DNA computing algorithm
• Edge-outer graph embedding and the complexity of the DNA reporter strand problem

This page was built for publication: Efficient DNA sticker algorithms for NP-complete graph problems

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