| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Research on DNA Computing Methods of Optimization Problems on Weighted Graph |
| Authors | HAN Ai-Li |
| Address | (School of Information Engineering, Shandong University at Weihai, Weihai, Shandong264209) |
| Year | 2008 |
| Issue | No.12(2182¡ª2192) |
| Abstract & Background | Abstract This paper discusses DNA computing methods of classical optimization problems on weighted graph. By improving the methods of encoding weights in the previous DNA computing model, this paper proposes some new DNA encoding methods and DNA algorithms for optimization problems. Specifically, by designing the relative length graph of a weighted and undirected graph, it gives a DNA encoding method and DNA algorithm based on relative length graph for the traveling salesman problem; by designing the general line graph of a weighted and undirected graph, gives a DNA encoding method and DNA algorithm based on general line graph for the Chinese postman problem; by selecting the best one of reverse complement alignments of DNA sequences, gives a DNA encoding method and DNA algorithm based on reverse complement alignment for the minimum spanning tree problem; by designing an improved polynomial transformation from the vertex cover problem to the Hamilton circle problem, gives a DNA encoding method and DNA algorithm based on polynomial transformation for the vertex cover problem. The proposed DNA computing methods improve the capability of representing and dealing with data in DNA computing. Keywords intelligent computing; DNA computing; algorithm; optimization problem; weighted graph |