Application of DNA computing in graph theory

被引：10

作者：

Eghdami, Hossein ^{[2
]}

Darehmiraki, Majid ^{[1
]}

机构：

[1] Khatam Alanbia Univ Technol, Dept Math, Behbahan, Khouzestan, Iran

[2] Univ Birjand, Dept Math, Birjand, Iran

来源：

ARTIFICIAL INTELLIGENCE REVIEW | 2012年 / 38卷 / 03期

关键词：

DNA computing; NP-complete; Graph theory;

D O I：

10.1007/s10462-011-9247-5

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Although DNA computing was rapidly discarded when researchers realized some of the drawbacks related to it, but by computer simulation of molecular reaction it may be implemented in silico by computer architectures offering massive parallelism. In this review, we describe sticker algorithm for several famous graph problem. Presented algorithms have polynomial time complexity.

引用

页码：223 / 235

页数：13

共 13 条

[1] Computing with DNA [J].

Adleman, LM .

SCIENTIFIC AMERICAN, 1998, 279 (02) :54-61

[2] MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS [J].

ADLEMAN, LM .

SCIENCE, 1994, 266 (5187) :1021-1024

[3] Topics in the theory of DNA computing [J].

Amos, M ;

Paun, G ;

Rozenberg, G ;

Salomaa, AT .

THEORETICAL COMPUTER SCIENCE, 2002, 287 (01) :3-38

[4] A New Solution for Maximal Clique Problem based Sticker Model [J].

Darehmiraki, Majid .

BIOSYSTEMS, 2009, 95 (02) :145-149

[5] Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing [J].

Guo, MY ;

Chang, WL ;

Ho, MC ;

Lu, J ;

Cao, JN .

BIOSYSTEMS, 2005, 80 (01) :71-82

[6] Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing [J].

Guo, MY ;

Ho, MSH ;

Chang, WL .

PARALLEL COMPUTING, 2004, 30 (9-10) :1109-1125

[7] A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers [J].

Hsieh, Sun-Yuan ;

Chen, Ming-Yu .

APPLIED MATHEMATICS AND COMPUTATION, 2008, 197 (02) :672-686

[8]

Minyi Guo, 2004, International Journal of High Performance Computing and Networking, V1, P128

[9]

QIU ZF, 2003, APPL SOFT COMPUT, V3, P177

[10] A DNA procedure for solving the shortest path problem [J].

Wang, Zhaocai ;

Xiao, Dongmei ;

Li, Wenxia ;

He, Lin .

APPLIED MATHEMATICS AND COMPUTATION, 2006, 183 (01) :79-84

← 1 2 →