Open AccessStar Coloring Problem: The DNA Solution
Author(s) -
G. Sethuraman,
Kavitha Mulackampilly Joseph
Publication year - 2012
Publication title -
international journal of information technology and computer science
Language(s) - English
Resource type - Journals
eISSN - 2074-9015
pISSN - 2074-9007
DOI - 10.5815/ijitcs.2012.03.05
Subject(s) - computer science , star (game theory) , astrophysics , physics
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 (n), where n is the number of vertices of the graph.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom