Abstract

With the increasing popularity of interconnection networks, efficient information dissemination has become a popular research area. Broadcasting is one of the information dissemination primitives. Finding the optimal broadcasting scheme for any originator in an arbitrary network has been proved to be an NP-Hard problem. In this thesis, a new heuristic that generates broadcast schemes in arbitrary networks is presented, which has O(|E| + |V | log |V |) time complexity. Based on computer simulations of this heuristic in some commonly used topologies and network models, and comparing the results with the best existing heuristics, we conclude that the new heuristic show comparable performances while having lower complexity.