DNA Computing towards the Solution of Minimum Vertex Cover Problem
DOI:
https://doi.org/10.61841/hvrmb691Keywords:
Adleman-Lipton Model, Parallel Computing, MVCP, Watson-Crick Complementarity, NPComplete Problem, DNA ComputingAbstract
DNA computing is an unconventional method for parallel computation. It is a technique proposed for finding a solution to intractable computational problems. A computational hard problem in which the time complexity can increase exponentially with problem size. This work develops a new DNA-exploring model to solve a minimum vertex cover problem (MVCP). This DNA processing model solves the MVCP in polynomial time calculation.
Downloads
References
[1] Garey, M.R., Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-completeness. (W.H. Freeman and Company, 1979).
[2] L.M. Adleman, Molecular computation of solution to combinatorial problems, Science 1994, vol. 266, pp.
1021-1024.
[3] R.J. Lipton, DNA solution of HARD computational problems, Science, 199, vol. 268, pp. 542-545.
[4] W.X. Li, D.M. Xiao, L. He, DNA ternary addition, Applied Mathematics and Computation 2006, vol.2, pp. 977-986.
[5] D.M. Xiao, W.X. Li, J. Yu, X.D. Zhang, Z.Z. Zhang, L. He, Procedures for a dynamical system on {0,1}
with DNA molecules, BioSystems 2006, vol. 84, pp. 207-216.
[6] X.L. Wang, Z.M. Bao, J.J. Hu, S. Wang, A. Zhan, Solving the SAT problem using a DNA computing
algorithm based on ligase chain reaction, BioSystems 2008, vol. 91, pp. 117-125.
[7] R.M. Karp, “Reducibility among combinatorial problems,” In 50 Years of Integer Programming 1958-
2008, Springer Press, 2010, pp. 219-241.
[8] R. Niedermeier, P. Rossmanith, “Upper bounds for vertex cover further improved,” Proceedings of the 16th
International Symposium on Theoretical Aspects of Computer Science (STACS), Springer Press, 1999, pp.
561–570.
[9] S. Khuri, Th. Back, “An evolutionary heuristic for the minimum vertex cover problem,” Proceedings of the 18th German Annual Conference on Artificial Intelligence, September 1998, pp. 86-904.
[10] G. Sethuraman and J. Kavitha, “Star Coloring Problem: The DNA Solution,” International Journal of Information Technology and Computer Science 2012, vol. 3, 31-37.
[11] J. Kavitha, “Fast Parallel DNA Solution to Oriented Coloring Problem,” International Journal of Advanced Research in Engineering and Technology 2017, vol. 8, 3, 12-18.
Downloads
Published
Issue
Section
License
Copyright (c) 2020 AUTHOR
This work is licensed under a Creative Commons Attribution 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
- Adapt — remix, transform, and build upon the material for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
- Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
