Fast Parallel Solution for Set-Packing and Clique Problems by DNA-Based Computing(Scientific and Engineering Computing with Applications)(<Special Section>Hardware/Software Support for High Performance Scientific and Engineering Computing)
スポンサーリンク
概要
- 論文の詳細を見る
This paper shows how to use sticker to construct solution space of DNA for the library sequences in the set-packing problem and the clique problem. Then, with biological operations, we propose DNA-based algorithms to remove illegal solutions and to find legal solutions for the set-packing and clique problems from the solution space of sticker. Any NP-complete problem in Cook's Theorem can be reduced and solved by the proposed DNA-based computing approach if its size is equal to or less than that of the set-packing problem. Otherwise, Cook's Theorem is incorrect on DNA-based computing and a new DNA algorithm should be developed from the characteristics of the NP-complete problem. Finally, the result to DNA simulation is given.
- 社団法人電子情報通信学会の論文
- 2004-07-01
著者
-
GUO Minyi
Department of Computer Science and Engineering, Shanghai Jiao Tong University
-
HO Michael
Department of Pathology, The Hospital for Sick Children
-
YANG Laurence
Department of Computer Science, St. Francis Xavier University
-
Guo Minyi
Department Of Computer Science And Engineering Shanghai Jiao Tong University
-
Ho Michael
Department Of Information Management Southern Taiwan University Of Technology
-
Yang Laurence
Department Of Computer Science St. Francis Xavier University
-
CHANG Weng-Long
Department of Information Management, Southern Taiwan University of Technology
-
Chang Weng-long
Department Of Information Management Southern Taiwan University Of Technology
-
GUO Minyi
Department of Computer Software, The University of Aizu
関連論文
- Trusted Routing Based on Dynamic Trust Mechanism in Mobile Ad-Hoc Networks
- Giant cells in cortical tubers in tuberous sclerosis showing synaptophysin-immunoreactive halos
- Allocation of Tasks in a DCS Using a Different Approach with A^* Considering Load(Distributed, Grid and P2P Computing)(Hardware/Software Support for High Performance Scientific and Engineering Computing)
- A Secure and Scalable Rekeying Mechanism for Hierarchical Wireless Sensor Networks
- Efficient Communication Optimization for Irregular Array References (ハイパフォーマンスコンピューティング研究報告 2001年並列/分散/協調処理に関する『沖縄』サマー・ワークショップ(SWoPP「沖縄」2001)--研究会・連続同時開催)
- Programming Support for MPMD Parallel Computing in ClusterGOP(Software Support and Optimization Techniques)(Hardware/Software Support for High Performance Scientific and Engineering Computing)
- Multipath Routing with Reliable Nodes in Large-Scale Mobile Ad-Hoc Networks
- Fast Parallel Solution for Set-Packing and Clique Problems by DNA-Based Computing(Scientific and Engineering Computing with Applications)(Hardware/Software Support for High Performance Scientific and Engineering Computing)
- Efficient Loop Partitioning for Parallel Codes of Irregular Scientific Computations(Software Systems)
- Optimization Techniques for Parallel Codes of Irregular Scientific Computations(Code Generation and Optimization)
- Tier-Based Scalable and Secure Routing for Wireless Sensor Networks with Mobile Sinks
- Evaluation of the Feedback Guided Dynamic Loop Scheduling (FGDLS) Algorithms(Distributed, Grid and P2P Computing)(Hardware/Software Support for High Performance Scientific and Engineering Computing)