DNA Solution of a Graph Coloring Problem

详细信息    查看全文

• 作者：Yachun Liu ; Jin Xu ; Linqiang Pan ; and Shiying Wang
• 刊名：Journal of Chemical Information and Modeling
• 出版年：2002
• 出版时间：May 2002
• 年：2002
• 卷：42
• 期：3
• 页码：524 - 528
• 全文大小：64K
• 年卷期：v.42,no.3(May 2002)
• ISSN：1549-960X

文摘

The graph-theoretic parameter that has probably received the most attention over the years is the chromaticnumber. As is well-known, the coloring problem is an NP-Complete problem. In this paper, it has beensolved by means of molecular biology techniques. The algorithm is highly parallel and has satisfactoryfidelity. This work shows further evidence for the ability of DNA computing to solve NP-Complete problems.