International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 4, No. 3, 8 Apr. 2012
Cover page and Table of Contents: PDF (size: 134KB)
Author(s)
G. Sethuraman
1,*
Kavitha Joseph
2
Index Terms
NP-complete problem, Star coloring problem, DNA based parallel algorithm, parallel computing, Polynomial time algorithm, Time complexity
Abstract
In this paper, a DNA based computing model for solving the star coloring problem is proposed. This model shows how to use DNA strands to construct solution space of molecules for the star coloring problem and how to apply the DNA algorithm to solve the star coloring problem using biological operations. The algorithm is highly parallel and has satisfactory fidelity. The time complexity of the algorithm is O (n2), where n is the number of vertices of the graph.
Cite This Paper
G. Sethuraman, Kavitha Joseph, "Star Coloring Problem: The DNA Solution", International Journal of Information Technology and Computer Science(IJITCS), vol.4, no.3, pp.31-37, 2012. DOI:10.5815/ijitcs.2012.03.05
Reference
[1]Adleman , L. Molecular solutions to combinatorial problems. Science. 1994, 266, 1021-1024.
[2]Sinden, R.R.: DNA structure and Function. Academic Press. New York. 1994
[3]Feynman, R.P. in Gilbert,D.H.(Ed.), Minaturization. Reinhold Publishing Corporation. New York. 1961,282-296
[4]Lipton, R.J.: DNA solution of hard computational problems. Science. 1995, 268, 542-545
[5]Roweis, S., Winfree, E., Burgoyne, R., Chelyapov, N.V., Goodman,M.F., Rothemund, P.W.K., Adleman,L.M. . A Sticker based model for DNA computation, in: Landweber,L., Baum, E.(Eds.), 2nd Annual Workshop on DNA Computing, DIMACS : Series in Discrete Mathematics and theoretical Computer science, American Mathematical Society, Princeton University. 1999, 1-29
[6]Boneh,D., Dunworth,C., Lipton,R.J., Sgall,J. : On the computational power of DNA, in. Discrete Applied Mathematics. Special Issue on Computational Molecular Biology. 1996, 71, 79-94
[7]Paun,G., Rozenberg,G., Salomaa,A. DNA Computing: New Computing Paradigm. Springer-Verlag. New York. 1998, ISBN : 3-540-64196-3
[8]Adleman,L.M. . On constructing a molecular computer, DNA Based Computers, in : Lipton,R., Baum,E.(Eds.), DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society. 1996, 1-21
[9]Garey,M.R., Johnson,D.S. Computer and intractability. Freeman, San Fransico, CA,1979
[10]Qinghua Liu. et al. DNA computing on surfaces, Nature. 2000, 403, 175-179
[11]Chee,M. et al. Accessing genetic information with high-density DNA arrays. Science 1996, 276 , 610-614 .
[12]Yu-Xing Yang, Ai-Min Wang, Ji-Ian Ma: Multi-separation based DNA algorithm of graph vertex coloring problem. 2008, ICNC 7, 547-550
[13]Ya Chun Liu et al. DNA solution of graph coloring problem. Journal of chemical information and modeling 2002, 42(3) , 524-528
[14]YMiniyi Guo et al. Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing. Bio systems. 2005, 80(1), 71-82
[15]Jiang Xingpeng et al. A new DNA algorithm to solve graph coloring problem. Progress in natural science 2007, 17(6), 733-738
[16]Wang.S, Yuan. J. DNA computing of directed line-graphs. Communication in mathematical and in computer chemistry 2006, 56(3), 479-484
[17]Israel Marck, K. H. Zimmermann. Parallel bioinspired algorithms for NP-complete graph problems. Journal of parallel and distributed computing 2009, 69(3), 221-229
[18]Weng-Long Cheng et al. Towards solution of the set-splitting problem on gel based DNA computing. Future generation computer systems 2004, 20(5), 875-885
[19]Xu Jin et al. A DNA computer model for solving vertex coloring problem. Chinese science bulletin 2006, 51(20), 2541-2549
[20]Zhiquan Frank Qiu, Mi Lu . A new approach to advance the DNA computing. Applied soft computing 2003, 3(2), 177-189