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 条
  • [41] A Polynomial-Time Algorithm Computing Lower and Upper Bounds of the Rooted Subtree Prune and Regraft Distance
    Kannan, Lavanya
    Li, Hua
    Mushegian, Arcady
    JOURNAL OF COMPUTATIONAL BIOLOGY, 2011, 18 (05) : 743 - 757
  • [42] A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs
    Lin, Min-Sheng
    Ting, Chao-Chun
    INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 371 - 376
  • [43] Efficient connectivity analysis in underwater wireless sensor networks: a polynomial-time solution for the connectivity between nodes
    Altherwy, Youssef N.
    INTERNATIONAL JOURNAL OF SENSOR NETWORKS, 2024, 46 (04) : 205 - 217
  • [44] A parallel biological computing algorithm to solve the vertex coloring problem with polynomial time complexity
    Wang, Zhaocai
    Wang, Dangwei
    Bao, Xiaoguang
    Wu, Tunhua
    JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2021, 40 (03) : 3957 - 3967
  • [45] Fast Polynomial Time Approximate Solution for 0-1 Knapsack Problem
    Wang, Zhengyuan
    Zhang, Hui
    Li, Yali
    COMPUTATIONAL INTELLIGENCE AND NEUROSCIENCE, 2022, 2022
  • [46] DNA Computing Solves the 3-SAT Problem with a Small Solution Space
    Wang, Xiaolong
    Bao, Zhenmin
    Hu, Jingjie
    Gou, Deming
    CURRENT NANOSCIENCE, 2008, 4 (04) : 354 - 360
  • [47] Molecular solution to the 0-1 knapsack problem based on DNA computing
    Darehmiraki, Majid
    Nehi, Hasan Mishmast
    APPLIED MATHEMATICS AND COMPUTATION, 2007, 187 (02) : 1033 - 1037
  • [48] Solution to the 0-1 Knapsack Problem based on DNA Encoding and Computing Method
    Ye, Lian
    Zhang, Min
    JOURNAL OF COMPUTERS, 2013, 8 (03) : 669 - 675
  • [49] A polynomial time algorithm for the minimum quartet inconsistency problem with O(n) quartet errors
    Wu, Gang
    You, Jia-Huai
    Lin, Guohui
    INFORMATION PROCESSING LETTERS, 2006, 100 (04) : 167 - 171
  • [50] Heuristic solution to a 10-city asymmetric traveling salesman problem using Probabilistic DNA computing
    Spetzler, David
    Xiong, Fusheng
    Frasch, Wayne D.
    DNA COMPUTING, 2008, 4848 : 152 - +
12345