Abstract

Broadcasting is a fundamental information dissemination problem, wherein a message is sent from one vertex, the originator, to all other vertices in a graph. In k -broadcasting, an informed vertex can sends the message to at most k uninformed neighbors in each time unit. This thesis presents several algorithms to perform efficient k -broadcasting. The algorithm KBT generates the optimal k -broadcast scheme in trees, while the algorithm KBC finds the k -broadcast center of a given tree. This thesis presents an efficient heuristic for k -broadcasting. The heuristic has a low time complexity and generates fast k -broadcast schemes in many network topologies. A k -broadcast graph G is a graph on n vertices where the k -broadcast time of G is [Special characters omitted.] log k +1 n [Special characters omitted.] . B k (n) stands for the minimum possible number of edges in a k -broadcast graph on n vertices. A k -broadcast graph on n vertices with B k (n) edges is a minimum k -broadcast graph, which is denoted by k -mbg. This thesis presents several new k -mbg's and an improved lower bound on B k (n)