Open AccessHamiltonian path problem solution using DNA computing
Author(s) -
Anna Sergeenko,
Maria Yakunina,
Oleg Granichin
Publication year - 2020
Publication title -
cybernetics and physics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 8
eISSN - 2226-4116
pISSN - 2223-7038
DOI - 10.35470/2226-4116-2020-9-1-69-74
Subject(s) - dna computing , hamiltonian path , hamiltonian path problem , computer science , path (computing) , upper and lower bounds , algorithm , hamiltonian (control theory) , mathematics , theoretical computer science , mathematical optimization , computation , graph , mathematical analysis , programming language
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.