Hamiltonian path problem: The performance comparison deoxyribonucleic acid computing and the branch-and-bound method

Результат исследований: Научные публикации в периодических изданияхстатья в журнале по материалам конференции

1 Цитирования (Scopus)

Аннотация

In this article different approaches to one of the most popular combinatorial problem - the Hamiltonian path problem - are illustrated and compared between each other. It is shown that it becomes inefficient to use branch-and-bound method, the most popular method which is realized on a computer, from the counted number of vertices because of its exponentially growing complexity, one more algorithm which is based on working with deoxyribonucleic acid (DNA) molecules in a laboratory is analysed. That method works parallel and has linearly growing time consumption. Due to the improvements in the biophysics methods, which are needed for DNA computing, that algorithm became much faster than it was several years ago and it is now possible to add some new stages in DNA computing, which are shown in this paper.

Язык оригиналаанглийский
Номер статьи012003
ЖурналJournal of Physics: Conference Series
Том1536
Номер выпуска1
DOI
СостояниеОпубликовано - 21 мая 2020
СобытиеInternational Workshop Navigation and Motion Control 2019, NMC 2019 - Ladoga Lake, Российская Федерация
Продолжительность: 16 сен 201920 сен 2019

Предметные области Scopus

  • Физика и астрономия (все)

Fingerprint Подробные сведения о темах исследования «Hamiltonian path problem: The performance comparison deoxyribonucleic acid computing and the branch-and-bound method». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать