Efficient DNA Algorithms for Chromatic Number of Graph Problems

摘要：

Adlemans successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing.The graph-theoretic parameter that has probably received the most attention over the years is the chromatic number.The coloring problem is an NP -Complete problem.We provide DNA algorithms based on the molecular biology techniques to compute the vertex chromatic number of a given graph.The algorithms determine not merely the existence of a solution but yield all solutions (if any). The algorithm is highly parallel and has satisfactory fidelity.This work represents further evidence for the ability of DNA computing to solve NP -Complete problems.

关键词： DNA Computing Vertex Coloring Chromatic Number Algorithm

作者: Liu Xikui Li Yan

作者单位: College of Information &Engineering Shandong University of Science and Technology Qingdao 266510,Shandong,P.R.China

会议类型: 国际会议

会议名称: 2007 IEEE International Conference on Automation and Lofistics

会议地点: 山东济南

会议语种:英文

在线出版日期: 2007-08-18（万方平台首次上网日期，不代表论文的发表时间）