Login | Register

Broadcasting in weighted-vertex graphs

Title:

Broadcasting in weighted-vertex graphs

Kamali, Shahin (2008) Broadcasting in weighted-vertex graphs. Masters thesis, Concordia University.

[img]
Preview
Text (application/pdf)
MR45337.pdf - Accepted Version
2MB

Abstract

In this thesis, we present a new model for information dissemination in communication networks. The model is defined on networks in which nodes are assigned some weights representing the internal delay they should pass before sending data to their neighbors. The new model, called weighted-vertex model, comes to have real world applications in parallel computation and satellite terrestrial networks. Broadcasting in weighted-vertex model is a generalized version of classical broadcasting problem, which is NP_Complete. The problem remains NP_Complete in some classes of weighed-vertex graphs. We show existence of approximation algorithms for the broadcasting problem in weighted vertex model, as well as better approximations for specific subclasses of weighted graphs. In addition we study broadcasting in complete weighted graphs and present an algorithm for finding the optimum solution in this case. Broadcasting in complete graphs with uniform weights is studied separately. Finally we introduce some heuristics for the problem and compare their performance using computer simulations.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Kamali, Shahin
Pagination:ix, 75 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Date:2008
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:976179
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:21
Last Modified:18 Jan 2018 17:41
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