Abstract

Finding the optimal broadcasting schedule in an arbitrary network is an NP-hard problem. Many papers have been published on the topic of finding an efficient and effective heuristic for broadcasting. In this thesis, a heuristic algorithm for broadcasting in arbitrary networks is presented. This heuristic is first tested in several commonly used graphs; such as Butterfly, CCC d , deBruijn and Shuffle Exchange . In these graphs, this heuristic generates almost the same broadcast schedules as the best existing heuristic for broadcasting. However, the time complexity of this heuristic is much lower. The heuristic is also tested in three of the best-known network design models, and the heuristic outperforms the best existing heuristic in these models. The time complexity of this heuristic is O ( R · m ), where R represents the rounds of broadcasting, and m stands for the total number of communication links in the network.