Breadcrumb

 
 

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.

[img]
Preview
PDF
2457Kb

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 > Faculty 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:Theses (M.Comp.Sc.)
Program:Computer Science and Software Engineering
Date:2002
Thesis Supervisor(s):Harutyunyan, Hovhannes A.
ID Code:2118
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:25
Last Modified:08 Dec 2010 10:24
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

Document Downloads

More statistics for this item...

Concordia University - Footer