Wang, Wei (2010) Heuristics for Message Broadcasting in Arbitrary Networks. Masters thesis, Concordia University.
|PDF - Accepted Version|
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, two new heuristics that generate broadcast schemes in arbitrary networks are presented. Both of them have O(|E|) time complexity. Moreover, in the broadcast schemes generated by the heuristics, each vertex in the network receives the message via a shortest path. Based on computer simulations of these heuristics in some commonly used topologies and network models, and comparing the results with the best existing heuristics, we conclude that the new heuristics show comparable performances while having lower complexity.
|Divisions:||Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering|
|Item Type:||Thesis (Masters)|
|Degree Name:||M. Comp. Sc.|
|Thesis Supervisor(s):||Harutyunyan, Hovhannes|
|Deposited By:||WEI WANG|
|Deposited On:||09 Jun 2011 15:48|
|Last Modified:||04 Jan 2012 15:21|
Repository Staff Only: item control page