图的最大权团的DNA计算

• 作者: 张强 许进 马润年 高琳
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: DNA计算 NP-完全问题 最大权团
• 年，卷（期）: 2004,（1）
• 所属期刊栏目: 学术论文
• 页码范围: 13-16
• 页数: 4页
• 分类号: TN4
• 字数: 4997字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2004.01.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张强	大连理工大学机械工程学院	76	619	14.0	20.0
5	高琳	西安电子科技大学计算机学院	43	810	16.0	28.0
6	马润年	空军工程大学电讯工程学院	44	217	9.0	13.0
7	许进	大连大学先进设计技术中心	2	66	2.0	2.0