Abstract
The le dissemination problem under the trust model is rst studied by Ku et al. (GLOBECOM 2012), who de ned 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.