DNA计算在图论与组合优化中的应用

The computer technique is thought one of three revolutions of science in the 20th century. It greatly accelerated the development of society. But quantum physics successfully forecasted that it is.impossible the timeless increase of capacity of chip. For this reason, scientists are investigating other completely new computer structure. In the recent years, the DNA computing received much concern of people. Although some progress is made in the research of DNA.computing, there are many experimental problems and theoretical problems needed to be solved. In this project, we use DNA.computing to solve problems in the graph theory and combinatorial optimization, and in this way, we investigate the DNA computing. The DNA algorithms are given of maximum clique problem, minimum vertex covering problem, maximum matching.problem in bipartite graphs, coloring problem, Chinese postman problem, and spanning tree problem. In the above algorithms, we especially investigate the error problem and feasibility problem..The obtained results are valuable reference for the design of the prototype of DNA computer

本项目是关于计算机科学、数学和生物学的综合性研究课题。拟用DNA计算机解决复杂计算侍猓缫恍┦涤眯訬P-完全问题：图着色、平面测试等；非线性优化和Ramsey数等，进一步研究分子计算系统中有效的生物技术，并将成果应用到诸如密码系统、调度系统、VSLI的自动化设计等领域，为用DNA计算机解决复杂计算问题打下坚实的基础。..