科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
