Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/60412
Title: Using sticker to solve the 3-dimensional matching problem in molecular supercomputers
Authors: Guo, M
Chang, WL
Cao, J 
Keywords: Molecular supercomputing
DNA-based parallel algorithms
NP-complete Hamiltonian path problem
Parallel computing
Three-dimensional matching
3D matching
NP-complete satisfiability
Sticker
Simulation
High performance computing
Issue Date: 2005
Publisher: InterScience
Source: International journal of high performance computing and networking, 2005, v. 1, no. 1-3, p. 128-139 How to cite?
Journal: International journal of high performance computing and networking 
Abstract: Adleman demonstrated that DNA (Deoxyribonucleic acid) strands could be applied for dealing with solutions to an instance of the NP-complete Hamiltonian path problem (HPP) (Adleman, 1994). The Adleman techniques could also be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete problem) (Lipton, 1995). Furthermore, sticker is used for enhancing the Adleman-Lipton model (Roweis et al., 1999). In this paper, we first use sticker to construct solution space of DNA library sequences for the 3-dimensional matching problem. Then, in the Adleman-Lipton model, we propose an algorithm to remove illegal solution and find legal solution for the 3-dimensional matching problem from solution space of sticker. Finally, a simulation result for our algorithm is generated.
URI: http://hdl.handle.net/10397/60412
ISSN: 1740-0562
DOI: 10.1504/IJHPCN.2004.007572
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

11
Last Week
2
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.