使用 DNA計算解決圖形上的成對支配問題 計算解決圖形上的成對支配問題

Abstract

本論文應用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 ).