Hamiltonian path problem solution using DNA computing

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In this article we study DNA computing, a method which is based on working with DNA molecules in a lab-oratory. 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 clas-sical 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 pa-per to compare its performance with the time consump-tion of DNA computing. The results of that compari-son 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.

Original languageEnglish
Pages (from-to)69-74
Number of pages6
JournalCybernetics and Physics
Volume9
Issue number1
StatePublished - 30 Jun 2020

Scopus subject areas

  • Signal Processing
  • Physics and Astronomy (miscellaneous)
  • Computer Vision and Pattern Recognition
  • Fluid Flow and Transfer Processes
  • Control and Optimization
  • Artificial Intelligence

Keywords

  • DNA
  • Evolutionary computation
  • Hamiltonian path
  • Optimization

Fingerprint

Dive into the research topics of 'Hamiltonian path problem solution using DNA computing'. Together they form a unique fingerprint.

Cite this