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

更新时间：2025-07-16

- Using DNA to Solve the Maximum Weight Clique of Graphs
- Acta Electronica Sinica Vol. 32, Issue 1, Pages: 13-16(2004)
- 作者机构：
  
  1. 空军工程大学电讯工程学院,陕西,西安,710077
  2. 大连理工大学机械工程学院,辽宁,大连,116024
  3. 大连大学先进设计技术中心,辽宁,大连,116622
  4. 西安电子科技大学计算机学院,陕西,西安,710071
  5. 空军工程大学电讯工程学院陕西西安,710077
  6. 大连理工大学机械工程学院辽宁大连,116024
  7. 大连大学先进设计技术中心辽宁大连,116622
  8. 西安电子科技大学计算机学院陕西西安,710071
- 作者简介：
- 基金信息：
- DOI：
  CLC： TN4
- Published：2004
- 稿件说明：
移动端阅览
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：

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

Views

1106

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Improving the Single Template Method in DNA Computing

A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy

Progress in the Research of DNA Computing

Analysis for Directed Hamilton Path Problems Based on Splicing Systems

A DNA Algorithm for Graph Vertex Coloring Problem

Related Author

ZHANG Lin-xi

ZHU Xiang-ou

LIU Wen-bin

WANG Xiang-hong

YANG Zhi-bang

YUE Guang-xue

LI Ken-li

ZHOU Xu

Related Institution

College of Physics and Electronic Information EngineeringWenzhou UniversityWenzhouZhejiang 325035China

Department of PhysicsZhejiang UniversityHangzhouZhejiang 310027China

Wenzhou Vocational and Technical CollageWenzhouZhejiang 325035China

College of Physics and Electronic Information Engineering,Wenzhou University

Department of Physics,Zhejiang University

⁰