Open AccessSolving Minimum Vertex Cover Problem Using DNA Computing
Author(s) -
Rofilde Hasudungan,
Dwi M. Pangestuty,
Asslia J. Latifah,
Rudiman
Publication year - 2019
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1361/1/012038
Subject(s) - vertex cover , dna computing , np complete , computation , vertex (graph theory) , set cover problem , edge cover , feedback vertex set , computer science , cover (algebra) , set (abstract data type) , algorithm , theoretical computer science , computational complexity theory , mathematics , mathematical optimization , approximation algorithm , graph , engineering , mechanical engineering , programming language
Minimum vertex cover problem is one of classical problem not only in mathematic but also in computer science. However, this problem considered as complex problem since is classify as NP-Hard. This paper proposed new technique based on DNA computing that has good capability to tacked parallel computation. This paper provide new DNA encoding and a set Bio-operation procedure to solve this problem. The result of this technique yield the correct optimum solution with better time complexity ( O (1)) compared the previous algorithms.