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)

Full work available at URL https://doi.org/10.1016/S0010-4655(02)00270-9

zbMATH Keywords

biomolecular computingDNA algorithmHamiltonian directed path problem

Mathematics Subject Classification ID

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

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

• 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
• 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?)

Cited in

(17)

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

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)