Hamiltonian path problem solution using DNA computing
Anna Sergeenko, Maria Yakunina, Oleg Granichin
In this article we study DNA computing, a method which is based on working with DNA molecules in a laboratory. That approach is implemented in solving one of the most popular combinatorial problem — the Hamiltonian path problem. Related to recent improvements in the biophysics methods, which are needed for DNA computing, we propose to change some steps in the classical
algorithm to increase accuracy of this method. The branch-and-bound method, the most popular method which is realized on a computer, is also shown in this paper to compare its performance with the time consumption of DNA computing. The results of that comparison prove that it becomes inefficient to use the branch-and-bound method from the counted number of vertices because of its exponentially growing complexity, while DNA computing works parallel and has linearly growing time consumption.
CYBERNETICS AND PHYSICS, Vol.9, No.1, 2020, 69-74, https://doi.org/10.35470/2226-4116-2020-9-1-69-74