- 學位論文
在信賴模型下有向無環圖之最佳傳播演算法
Optimal File Dissemination on DAG under the trust model
摘要
Ku 等作者在GLOBECOM 2012首先提出在信賴模型下的檔案傳輸問題。 他們把信賴關係定義成一棵完全二元樹並且設計了一個使用最少回數的方 法讓檔案從樹根傳至所有其他使用者。Tien 等作者(2016) 把信賴關係延 伸成有根的二元有向無環圖(DAG) 並且設計了較簡單的最佳回數演算法。 在本論文中,我們進一步把信賴關係延伸成一般的有向無環圖。我們證 明當有向無環圖的最大外分支度至少為6時,則找出使用最少回數的傳輸順 序將會是一個NP困難的問題。另一方面, 當信賴關係為一個一般樹,且 只有一個點的外分支度大於2時，則對於這個問題的一些特殊情形, 我們 提出了多項式時間的解法。最後, 對一般有根樹，我們設計了一個倍率為 mind f(d .. 1)(xd + 1)g 的近似演算法,其中, xd 是外分支度大於d 的節點 數。
並列摘要
The le dissemination problem under the trust model is rst studied by Ku et al. (GLOBECOM 2012), who dened the trust relationship as a full binary tree and design an algorithm to broadcast a le from the root to every user, using an optimal number of rounds. Tien et al. (2016) extended the trust relationship as a rooted binary DAG (Directed Acyclic Graph), and design conceptually simpler algorithms to compute an optimal-round broadcast. In this thesis, we further extend the trust model as a general-degree DAG. We will show that when the maximum degree of DAG is at least 6, nding an optimal schedule is a NP-hard problem. On the other hand, we also study a special case when the trust relationship is a general tree with only one node whose degree is greater than two. For such a problem, we show that we can solve it in polynomial time. Finally, we design a mind f(d..1)(xd +1)g-ratio approximation algorithm on general rooted tree T, where xd is the number of nodes whose degree is greater than d in T.