图的最大权团的DNA计算

Using DNA to Solve the Maximum Weight Clique of Graphs

给定顶点赋权的无向图 ,图的最大权团问题是寻找每个顶点都相邻的顶点子集 (团 )具有最大权 .这个问题是寻找无权图的最大团问题的推广 .图的最大团和最大权团都是著名的NP 完全问题 ,没有非常有效的算法 .1994年Adleman博士首先提出用DNA计算解决NP 完全问题 ,使得NP 完全问题的求解可能得到解决 .本文给出了基于质粒技术的无向图的最大权团问题的DNA算法 ,依据HeadT等的实验手段 ,本文提出的算法是有效并且可行的 .

Given an undirected graph with weights on the vertices, the maximum weight clique problem is to find a subset of mutually adjacent vertices (i.e., a clique) having the largest total weight. This problem is a generalization of the problem of finding the maximum cardinality clique of an unweighted graph. Owing to the maximum cardinality clique problem and the maximum weight clique problem of graphs to be NP-complete, there are no effective methods to solve these two problems. Doctor Adleman introduced firstly the DNA computing in 1994,with which the NP-complete problems are likely to be solved. This paper introduces the DNA solution to the Maximum Weight Clique Problem of an undirected graph based on the plasmoid. On the basis of Head T et al, the algorithm is an effective and feasible method.