Iranian Journal of Biotechnology, ( ISI ), Year (2020-6)

Title : ( Parallelizing Assignment Problem with DNA Strands )

Authors: babak khorsand , Abdorreza Savadi , Mahmoud Naghibzadeh ,

Access to full-text not allowed by authors

Citation: BibTeX | EndNote


Background: Many problems of combinatorial optimization, which are solvable only in exponential time, are known to be Non-Deterministic Polynomial hard (NP-hard). With the advent of parallel machines, new opportunities have been emerged to develop the effective solutions for NP-hard problems. However, solving these problems in polynomial time needs massive parallel machines and is not applicable up to now. Objectives: DNA (Deoxyribonucleic acid) computing provides a fantastic method to solve NP-hard problems in polynomial time. Accordingly, one of the famous NP-hard problems is assignment problem, which is designed to find the best assignment of n jobs to n persons in a way that it could maximize the profit or minimize the cost. Material and Methods: Applying bio molecular operations of Adelman Lipton model, a novel parallel DNA algorithm have been proposed for solving the assignment problem. Results: The proposed algorithm can solve the problem in O(n2) time complexity, and just O(n) initial DNA strand in comparison with ????^???? initial sequence, which is used by the other methods. Conclusions: In this article, using DNA computing, we proposed a parallel DNA algorithm to solve the assignment problem in linear time.


, DNA computing, Molecular computation, DNA algorithm, Adelman Lipton model, Assignment
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

author = {Khorsand, Babak and Savadi, Abdorreza and Naghibzadeh, Mahmoud},
title = {Parallelizing Assignment Problem with DNA Strands},
journal = {Iranian Journal of Biotechnology},
year = {2020},
month = {June},
issn = {1728-3043},
keywords = {DNA computing; Molecular computation; DNA algorithm; Adelman Lipton model; Assignment},


%0 Journal Article
%T Parallelizing Assignment Problem with DNA Strands
%A Khorsand, Babak
%A Savadi, Abdorreza
%A Naghibzadeh, Mahmoud
%J Iranian Journal of Biotechnology
%@ 1728-3043
%D 2020