Standard

Hamiltonian path problem solution using DNA computing. / Sergeenko, Anna; Yakunina, Maria; Granichin, Oleg.

In: Cybernetics and Physics, Vol. 9, No. 1, 30.06.2020, p. 69-74.

Research output: Contribution to journal › Article › peer-review

Harvard

Sergeenko, A, Yakunina, M & Granichin, O 2020, 'Hamiltonian path problem solution using DNA computing', Cybernetics and Physics, vol. 9, no. 1, pp. 69-74.

APA

Sergeenko, A., Yakunina, M., & Granichin, O. (2020). Hamiltonian path problem solution using DNA computing. Cybernetics and Physics, 9(1), 69-74.

Vancouver

Sergeenko A, Yakunina M, Granichin O. Hamiltonian path problem solution using DNA computing. Cybernetics and Physics. 2020 Jun 30;9(1):69-74.

Author

Sergeenko, Anna ; Yakunina, Maria ; Granichin, Oleg. / Hamiltonian path problem solution using DNA computing. In: Cybernetics and Physics. 2020 ; Vol. 9, No. 1. pp. 69-74.

BibTeX

@article{8ea0563dce584ebd8c61f6209ca60884,
title = "Hamiltonian path problem solution using DNA computing",
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.",
keywords = "DNA, Evolutionary computation, Hamiltonian path, Optimization",
author = "Anna Sergeenko and Maria Yakunina and Oleg Granichin",
year = "2020",
month = jun,
day = "30",
language = "English",
volume = "9",
pages = "69--74",
journal = "Cybernetics and Physics",
issn = "2223-7038",
publisher = "IPACS",
number = "1",

}

RIS

TY - JOUR

T1 - Hamiltonian path problem solution using DNA computing

AU - Sergeenko, Anna

AU - Yakunina, Maria

AU - Granichin, Oleg

PY - 2020/6/30

Y1 - 2020/6/30

N2 - 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.

AB - 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.

KW - DNA

KW - Evolutionary computation

KW - Hamiltonian path

KW - Optimization

UR - http://www.scopus.com/inward/record.url?scp=85087357719&partnerID=8YFLogxK

UR - https://www.elibrary.ru/item.asp?id=43304164

M3 - Article

AN - SCOPUS:85087357719

VL - 9

SP - 69

EP - 74

JO - Cybernetics and Physics

JF - Cybernetics and Physics

SN - 2223-7038

IS - 1

ER -

ID: 60761380