Login | Register

Heuristics for Message Broadcasting in Arbitrary Networks


Heuristics for Message Broadcasting in Arbitrary Networks

Wang, Wei (2010) Heuristics for Message Broadcasting in Arbitrary Networks. Masters thesis, Concordia University.

Text (application/pdf)
Wang_MCompSc_S2011.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 > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Wang, Wei
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:7211
Deposited By: WEI WANG
Deposited On:09 Jun 2011 19:48
Last Modified:18 Jan 2018 17:30
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top