A Polynomial-Time DNA Computing Solution for the N-Queens Problem

被引：5

作者：

Maazallahi, Ramin ^{[1
]}

Niknafs, Aliakbar ^{[1
]}

Arabkhedri, Paria ^{[1
]}

机构：

[1] Shahid Bahonar Univ Kerman, Dept Comp Engn, Kerman, Iran

来源：

2ND WORLD CONFERENCE ON EDUCATIONAL TECHNOLOGY RESEARCH | 2013年 / 83卷

关键词：

DNA computing; Adleman-Lipton Model; N-queens problem; NP-Complete; ALGORITHMS;

D O I：

10.1016/j.sbspro.2013.06.118

中图分类号：

G40 [教育学];

学科分类号：

040101 ; 120403 ;

摘要：

The N-queens problem is a classic combinatorial problem that there is no polynomial time solution for it in silicon based computers. It belongs to the set of NP-Complete problems and needs a plenty of calculations. On the other hand, it has been evidenced that DNA computing is able to solve such complex problems efficiently. In this paper we propose a method based on Adleman-Lipton model, a model of DNA computing, which is able to solve the N-queens problem in a polynomial time complexity. It provides all the solutions and runs in O(N-2). (C) 2013 The Authors. Published by Elsevier Ltd.

引用

页码：622 / 628

页数：7

共 50 条

[31] Hysteretic Hopfield network with dynamic tunneling for crossbar switch and N-queens problem
Thangavel, P.
Gladis, D.
NEUROCOMPUTING, 2007, 70 (13-15) : 2544 - 2551
[32] A general resolution of intractable problems in polynomial time through DNA Computing
Sanches, C. A. A.
Soma, N. Y.
BIOSYSTEMS, 2016, 150 : 119 - 131
[33] BINARY NEURAL-NETWORK WITH NEGATIVE SELF-FEEDBACK AND ITS APPLICATION TO N-QUEENS PROBLEM
OHTA, M
OGIHARA, A
FUKUNAGA, K
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1994, E77D (04) : 459 - 465
[34] A Polynomial-Time Approximation Scheme for the Euclidean Problem on a Cycle Cover of a Graph
Khachai, M. Yu.
Neznakhina, E. D.
PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS, 2015, 289 : S111 - S125
[35] A POLYNOMIAL-TIME ALGORITHM FOR THE LOCAL TESTABILITY PROBLEM OF DETERMINISTIC FINITE AUTOMATA
KIM, SM
MCNAUGHTON, R
MCCLOSKEY, R
IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (10) : 1087 - 1093
[36] Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
Hallgren, Sean
JOURNAL OF THE ACM, 2007, 54 (01)
[37] RETRACTED: One Eighth Rule in N-queens Problem Based on Group Theory and Morphological Gene Combinations (Retracted Article)
Zhang Dakun
2009 INTERNATIONAL FORUM ON INFORMATION TECHNOLOGY AND APPLICATIONS, VOL 3, PROCEEDINGS, 2009, : 651 - +
[38] Parallel genetic algorithm for N-Queens problem based on message passing interface-compute unified device architecture
Cao Jianli
Chen Zhikui
Wang Yuxin
Guo He
COMPUTATIONAL INTELLIGENCE, 2020, 36 (04) : 1621 - 1637
[39] A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation
Mukherjee, M
Chakraborty, K
INFORMATION PROCESSING LETTERS, 2002, 83 (01) : 41 - 48
[40] A POLYNOMIAL-TIME ALGORITHM FOR THE PERFECT PHYLOGENY PROBLEM WHEN THE NUMBER OF CHARACTER STATES IS FIXED
AGARWALA, R
FERNANDEZBACA, D
SIAM JOURNAL ON COMPUTING, 1994, 23 (06) : 1216 - 1224

← 1 2 3 4 5 →