Login | Register

A heuristic for broadcasting in arbitrary networks


A heuristic for broadcasting in arbitrary networks

Shao, Bin (2002) A heuristic for broadcasting in arbitrary networks. Masters thesis, Concordia University.

Text (application/pdf)


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 > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Shao, Bin
Pagination:xi, 90 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Harutyunyan, Hovhannes A.
ID Code:2118
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:25
Last Modified:18 Jan 2018 17:18
Related URLs:
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