As a famous problem in Combinatorics, small Ramsey number is very hard to solve, because it needs to enumerate all possible graphs in exponential time. We propose a new DNA algorithm for constructing Ramsey graphs, which is a complete process for a small-scale instance to construct all the R(3,3)-graphs of order five from theory to experiment. Based on in-depth analysis of Ramsey graph and bio-manipulation, our method can eliminate infeasible solutions in advance, and decrease enumeration greatly. Finally, there is a comparison with other methods and some suggestions on improving our method, both theoretically and experimentally. This article demonstrates that how to optimize computing process with constraints on DNA computing, which is also a novel attempt to construct Ramsey graph. More R(3,k)-graphs on larger scale can be computed by the proposed method.
展开▼
