Login | Register

A heuristic for broadcasting in arbitrary networks

Title:

A heuristic for broadcasting in arbitrary networks

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

[thumbnail of MQ77719.pdf]
Preview
Text (application/pdf)
MQ77719.pdf
2MB

Abstract

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
Date:2002
Thesis Supervisor(s):Harutyunyan, Hovhannes A.
Identification Number:T 57.84 S43 2002
ID Code:2118
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:25
Last Modified:13 Jul 2020 19:51
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

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top