图的最大权团的DNA计算

马润年; 张 强; 高 琳; 许 进

您当前的位置：

首页 >

文章列表页 >

图的最大权团的DNA计算

论文 | 更新时间：2025-07-16

- 图的最大权团的DNA计算
- Using DNA to Solve the Maximum Weight Clique of Graphs
- 电子学报 2004年32卷第1期页码：13-16
- 作者机构：
  
  1. 空军工程大学电讯工程学院,陕西,西安,710077
  2. 大连理工大学机械工程学院,辽宁,大连,116024
  3. 大连大学先进设计技术中心,辽宁,大连,116622
  4. 西安电子科技大学计算机学院,陕西,西安,710071
  5. 空军工程大学电讯工程学院陕西西安,710077
  6. 大连理工大学机械工程学院辽宁大连,116024
  7. 大连大学先进设计技术中心辽宁大连,116622
  8. 西安电子科技大学计算机学院陕西西安,710071
- 作者简介：
- 基金信息：
  
  国家自然科学基金 (No.69971018);陕西省自然科学基金 (No.2001X05)
- DOI：
  中图分类号： TN4
- 纸质出版：2004
- 稿件说明：
移动端阅览
马润年, 张强, 高琳, 等. 图的最大权团的DNA计算[J]. 电子学报, 2004,32(1):13-16.

MA Run-nian, ZHANG Qiang, GAO Lin, et al. Using DNA to Solve the Maximum Weight Clique of Graphs[J]. Acta Electronica Sinica, 2004, 32(1): 13-16.
马润年, 张强, 高琳, 等. 图的最大权团的DNA计算[J]. 电子学报, 2004,32(1):13-16. DOI：

MA Run-nian, ZHANG Qiang, GAO Lin, et al. Using DNA to Solve the Maximum Weight Clique of Graphs[J]. Acta Electronica Sinica, 2004, 32(1): 13-16. DOI：

摘要

给定顶点赋权的无向图

图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP-完全问题

没有非常有效的算法.1994年Adleman博士首先提出用DNA计算解决NP-完全问题

使得NP-完全问题的求解可能得到解决.本文给出了基于质粒技术的无向图的最大权团问题的DNA算法

依据Head T等的实验手段

本文提出的算法是有效并且可行的.

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

references

浏览量

1106

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

DNA计算中的单模板编码方法改进研究

一种基于分治的三维匹配问题DNA计算算法

DNA计算的研究进展

基于剪接系统的有向哈密顿路问题分析

图的顶点着色问题的DNA算法