請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69482完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳建輝 | |
| dc.contributor.author | Ying-Chieh Chen | en |
| dc.contributor.author | 陳英傑 | zh_TW |
| dc.date.accessioned | 2021-06-17T03:16:57Z | - |
| dc.date.available | 2021-07-06 | |
| dc.date.copyright | 2018-07-06 | |
| dc.date.issued | 2018 | |
| dc.date.submitted | 2018-07-03 | |
| dc.identifier.citation | [1] T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, 3th ed., Cambridge, Mass: MIT Press, 2009, pp. 587-748.
[2] T.W. Haynes and P.J. Slater, “Paired-domination in graphs,” Networks, vol. 32, pp. 199–206, 1998. [3] G. Păun, G. Rozenberg, and A. Salomaa, DNA Computing: New Computing Paradigms. Berlin, Germany: Springer-Verlag Berlin Heidelberg, 1998, pp. 117–149. [4] R.P. Feynman, “In miniaturization,” Engineering and Science, pp. 22–36, 1961. [5] L.M. Adleman., “Molecular computation of solutions to combinatorial problems,” Science, vol. 266, pp. 1021–1024, 1994. [6] Q. Ouyang, “DNA solution of the maximal clique problem,” Science, vol. 278, pp. 446-449, 1997. [7] S. Roweis1, E. Winfree1, R Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund, and L. M. Adleman, “A sticker based model for DNA computation,” Journal of Computational Biology, vol. 5, pp. 615-629, 1998 [8] R. J. Lipton, D. Boneh, and C. Dunworth, “Breaking DES using a molecular computer,” Discrete Applied Mathematics, vol. 71, pp. 79-94, 1996. [9] X. Zhou, G. G. Yue, Z. B. Yang, and K. L. Li, “A new approach for the dominating-set problem by DNA-based supercomputing,” Journal of software, vol. 5, pp. 662-670, 2010. [10] M. Guo, W.L. Chang, M. Ho, J. Lu, and J. Cao, “Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing,” BioSystems, vol. 80, pp. 71–82, 2005. [11] W.L. Chang, M. Guo, and J. Cao, “Using sticker to solve the 3-dimensional matching problem in molecular supercomputers,” International Journal of High Performance Computing and Networking, vol. 1, pp. 128-139, 2004. [12] L. Y. Kanga, M. Y. Sohnb, and T.C.E. Cheng, 'Paired-domination in inflated graphs,' Theoretical Computer Science, vol. 320, pp. 485-494, 2004. [13] Paul Dorbec, Sylvain Gravier, and Michael A. Henning, 'Paired-domination in generalized claw-free graphs,' Journal of Combinatorial Optimization, vol. 14, pp. 1-7, 2007. [14] J. Elbaz, O. Lioubashevski, F. Wang, F. Remacle, R. D. Levine, and I. Willner, 'DNA computing circuits using libraries of DNAzyme subunits,' Nature Nanotechnology, vol. 5, pp. 417-422, 2010. [15] L. kari, DNA Computing: Arrival of Biological Mathematics. New York, USA: Springer-Verlag New York, vol. 5, 1997, pp. 9-22. [16] M. Mucha and P. Sankowski, 'Maximum matchings via gaussian elimination,' Algorithmica, vol. 45, pp. 3-20, 2006. [17] A. Madry, 'Navigating central path with electrical flows: from flows to matchings, and back,' IEEE Symposium, vol. 54, pp. 253–262, 2013. [18] C. R. Kothari, D. J. Russomanno, and R. J. Deaton, 'Solution of the hamiltonian path problem: a sequential simulation inspired by DNA computing versus a classical method,' Memphis Univ., Memphis, TN, USA, Arkansas Univ., Arkansas, AR, USA, 2014. [19] W. L. Chang, S. C. Huang, K. W. Lin, and S. H. Ho, 'Fast parallel DNA-based algorithms for molecular computation: discrete logarithm,' J Supercomput, vol. 56, pp. 129-163, 2011. [20] M. Y. Guo, S. H. Ho, and W. L. Chang, 'Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing,' Parallel Computing, vol. 30, pp. 1109-1125, 2004. [21] H. Qiao, L. y. Kang, M. Cardei, and D. Z. Du, 'Paired-domination of trees,' Journal of Global Optimization, vol. 25, pp. 43-54, 2003. [22] M. Yannakakis and F. Gavril, 'Edge Dominating Sets in Graphs,' SIAM Journal on Applied Mathematics, vol. 38, pp. 364-372, 1980. [23] I. Bezáková, D. Štefankovič, V. V. Vazirani, and E. Vigoda, 'Accelerating simulated annealing for the permanent and combinatorial counting problems,' SIAM Journal on Computing, vol. 37, pp. 1429-1454, 2008. [24] R. F. T. S. Wagner, 'Extremal problems for topological indices in combinatorial chemistry,' Journal of Computational Biology, vol. 12, pp. 1004-1013, 2005. [25] L. Lovász, 'A characterization of perfect graphs,' Journal of Combinatorial Theory, vol. 13, pp. 95-98, 1972. [26] W. T. Tutte, 'A two-connected planar graph without concurrent longest paths,' Journal of Combinatorial Theory, vol. 13, pp.116-121, 1972. [27] C. T. Benson and J. B. Jacobs, 'On hearing the shape of combinatorial drums,' Journal of Combinatorial Theory, vol. 13, pp.170-178, 1972. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69482 | - |
| dc.description.abstract | 本論文應用DNA Computing, 設計一個演算法以解決圖上的成對支配問題。在本研究中，所有討論的圖均為由點和邊構成的無向、無環、有限點數的圖。支配集為圖上的點的子集合，此子集合的特點為圖上所有的點要不是在此集合內就是有一個或以上的鄰居在此集合內。一張圖上的成對支配集和並非唯一，故本演算法的價值就在於找到圖上點數最少的成對支配點集。
本研究使用DNA Computing的技術，並採用Sticker模型來進行本演算法的設計，我們取其能支援大量平行運算的特性，將原本為NP-Complete的圖上成對支配問題在多項式數量的生物基本操作內解決。本演算法的操作複雜度為 Θ(n^3 )。 | zh_TW |
| dc.description.abstract | In this thesis, we apply DNA computing technic to solve the paired-dominating set problem on graphs and the graphs we discussed in this thesis are all undirected and non-cyclic and with limited vertex number. V(G) is the vertex set of graph G = (V, E). A dominating set S of a graph G is a vertex subset such that, S⊆V(G), and each vertex in V(G) is either in S or is adjacent to at least one vertex in S. In addition, S is a paired-dominating set if the subgraph of G induced by S has a perfect matching. Our goal is aiming to find the minimum cardinality paired-dominating set on graphs. We proposed an algorithm using the DNA computing technic with sticker model to solve the problem with large input in polynomial basic biochemistry operations. The operation complexity is Θ(n^3 ). | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T03:16:57Z (GMT). No. of bitstreams: 1 ntu-107-R04944035-1.pdf: 2718658 bytes, checksum: ad0b25f2e79399b5e7a45bb8ae3a175d (MD5) Previous issue date: 2018 | en |
| dc.description.tableofcontents | 致謝 ....................................................................................................................................................... iii
中文摘要 ................................................................................................................................................ v Abstract ................................................................................................................................................ vii Chapter 1 Introduction ..................................................................................................................... 1 1.1 Preliminaries .................................................................................................... 1 Chapter 2 Computation Model ........................................................................................................ 3 2.1 DNA Computing .............................................................................................. 3 2.2 The Sticker Model ............................................................................................ 4 2.3 The Adleman-Lipton Model............................................................................ 7 Chapter 3 Solving the Paired-dominating Set Problem by DNA-Based Computing ................ 11 3.1 Generating all vertex subsets ........................................................................ 12 An example .......................................................................................................... 14 3.2 Generating paired part for each DNA strand ............................................. 18 3.3 Removing DNA strands without symmetry property ................................. 26 3.4 Removing DNA strands without matching property .................................. 32 3.5 Removing DNA strands without domination property .............................. 40 3.6 Finding all minimum paired-dominating sets ............................................. 52 Chapter 4 Conclusion ...................................................................................................................... 59 Bibliography ........................................................................................................................................ 60 | |
| dc.language.iso | en | |
| dc.subject | Sticker 模型 | zh_TW |
| dc.subject | 剪枝策略 | zh_TW |
| dc.subject | 成對支配問題 | zh_TW |
| dc.subject | DNA 計算 | zh_TW |
| dc.subject | DNA computing | en |
| dc.subject | sticker model | en |
| dc.subject | paired-domination | en |
| dc.subject | pruning strategy | en |
| dc.title | 使用 DNA計算解決圖形上的成對支配問題 計算解決圖形上的成對支配問題 | zh_TW |
| dc.title | Solving the Paired-Dominating Set Problem on Graphs by DNA Computing | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 106-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 林清池,周信宏 | |
| dc.subject.keyword | DNA 計算,Sticker 模型,成對支配問題,剪枝策略, | zh_TW |
| dc.subject.keyword | DNA computing,sticker model,paired-domination,pruning strategy, | en |
| dc.relation.page | 62 | |
| dc.identifier.doi | 10.6342/NTU201701859 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2018-07-03 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
| 顯示於系所單位： | 資訊網路與多媒體研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-107-1.pdf 未授權公開取用 | 2.65 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。