| [176958] |
| Title: Parallel bioinspired algorithms for NP complete graph problems. |
| Written by: Israel Marck Martinez-Perez and Karl-Heinz Zimmermann |
| in: <em>Journal of Parallel and Distributed Computing (JPDC)</em>. March (2009). |
| Volume: <strong>69</strong>. Number: (3), |
| on pages: 221-229 |
| Chapter: |
| Editor: |
| Publisher: Elsevier: |
| Series: |
| Address: |
| Edition: |
| ISBN: 10.1016/j.jpdc.2008.06.014 |
| how published: 09-85 MaZi09 JPDC |
| Organization: |
| School: |
| Institution: |
| Type: |
| DOI: |
| URL: |
| ARXIVID: |
| PMID: |
Note: khzimmermann, AEG
Abstract: It is no longer believed that DNA computing will outperform digital computers when it comes to the computation of intractable problems. In this paper, we emphasise the in silico implementation of DNA-inspired algorithms as the only way to compete with other algorithms for solving NP-complete problems. For this, we provide sticker algorithms for some of the most representative NP-complete graph problems. The simple data structures and bit-vertical operations make them suitable for some parallel architectures. The parallel algorithms might solve either moderate-size problems in an exact manner or, when combined with a heuristic, large problems in polynomial time.