首页 | 官方网站   微博 | 高级检索  
     

图的最大权团的DNA计算
引用本文:马润年,张强,高琳,许进.图的最大权团的DNA计算[J].电子学报,2004,32(1):13-16.
作者姓名:马润年  张强  高琳  许进
作者单位:1. 空军工程大学电讯工程学院,陕西西安 710077;2. 大连理工大学机械工程学院,辽宁大连 116024;3. 大连大学先进设计技术中心,辽宁大连 116622;4. 西安电子科技大学计算机学院,陕西西安 710071
基金项目:国家自然科学基金,陕西省自然科学基金
摘    要:给定顶点赋权的无向图,图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP-完全问题,没有非常有效的算法.1994年Adleman博士首先提出用DNA计算解决NP-完全问题,使得NP-完全问题的求解可能得到解决.本文给出了基于质粒技术的无向图的最大权团问题的DNA算法,依据Head T等的实验手段,本文提出的算法是有效并且可行的.

关 键 词:DNA计算  NP-完全问题  最大权团  
文章编号:0372-2112(2004)01-0013-04
收稿时间:2002-04-11

Using DNA to Solve the Maximum Weight Clique of Graphs
MA Run-nian,ZHANG Qiang ,GAO Lin,XU Jin.Using DNA to Solve the Maximum Weight Clique of Graphs[J].Acta Electronica Sinica,2004,32(1):13-16.
Authors:MA Run-nian  ZHANG Qiang    GAO Lin  XU Jin
Affiliation:1. The Telecommunication Engineering Institute,Air Force Engineering University,Xi'an ,Shaanxi 710077,China;2. School of Mechanical Engineering,Dalian University of Technology,Dalian,Liaoning 116024,China;3. Advanced Design Technology Center,Dalian University,Dalian,Liaoning 116622,China;4. School of Computer,Xidian University,Xi'an,Shaanxi 710071,China
Abstract: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.
Keywords:DNA computing  NP-complete problem  maximum weight clique
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《电子学报》浏览原始摘要信息
点击此处可从《电子学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号