Please use this identifier to cite or link to this item:
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
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.
ISSN: 1740-0562
DOI: 10.1504/IJHPCN.2004.007572
Appears in Collections:Journal/Magazine Article

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

Page view(s)

Last Week
Last month
Citations as of Aug 20, 2018

Google ScholarTM



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