Shao, Bin (2002) A heuristic for broadcasting in arbitrary networks. Masters thesis, Concordia University.
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.
|Divisions:||Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering|
|Item Type:||Thesis (Masters)|
|Pagination:||xi, 90 leaves : ill. ; 29 cm.|
|Degree Name:||Theses (M.Comp.Sc.)|
|Program:||Computer Science and Software Engineering|
|Thesis Supervisor(s):||Harutyunyan, Hovhannes A.|
|Deposited By:||Concordia University Libraries|
|Deposited On:||27 Aug 2009 17:25|
|Last Modified:||08 Dec 2010 15:24|
Repository Staff Only: item control page