請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69482
標題: | 使用 DNA計算解決圖形上的成對支配問題 計算解決圖形上的成對支配問題 Solving the Paired-Dominating Set Problem on Graphs by DNA Computing |
作者: | Ying-Chieh Chen 陳英傑 |
指導教授: | 陳建輝 |
關鍵字: | DNA 計算,Sticker 模型,成對支配問題,剪枝策略, DNA computing,sticker model,paired-domination,pruning strategy, |
出版年 : | 2018 |
學位: | 碩士 |
摘要: | 本論文應用DNA Computing, 設計一個演算法以解決圖上的成對支配問題。在本研究中,所有討論的圖均為由點和邊構成的無向、無環、有限點數的圖。支配集為圖上的點的子集合,此子集合的特點為圖上所有的點要不是在此集合內就是有一個或以上的鄰居在此集合內。一張圖上的成對支配集和並非唯一,故本演算法的價值就在於找到圖上點數最少的成對支配點集。
本研究使用DNA Computing的技術,並採用Sticker模型來進行本演算法的設計,我們取其能支援大量平行運算的特性,將原本為NP-Complete的圖上成對支配問題在多項式數量的生物基本操作內解決。本演算法的操作複雜度為 Θ(n^3 )。 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 ). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69482 |
DOI: | 10.6342/NTU201701859 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf 目前未授權公開取用 | 2.65 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。