Login | Register

On K-broadcasting in graphs


On K-broadcasting in graphs

Shao, Bin (2006) On K-broadcasting in graphs. PhD thesis, Concordia University.

[thumbnail of NR16285.pdf]
Text (application/pdf)
NR16285.pdf - Accepted Version


Broadcasting is a fundamental information dissemination problem, wherein a message is sent from one vertex, the originator, to all other vertices in a graph. In k -broadcasting, an informed vertex can sends the message to at most k uninformed neighbors in each time unit. This thesis presents several algorithms to perform efficient k -broadcasting. The algorithm KBT generates the optimal k -broadcast scheme in trees, while the algorithm KBC finds the k -broadcast center of a given tree. This thesis presents an efficient heuristic for k -broadcasting. The heuristic has a low time complexity and generates fast k -broadcast schemes in many network topologies. A k -broadcast graph G is a graph on n vertices where the k -broadcast time of G is [Special characters omitted.] log k +1 n [Special characters omitted.] . B k (n) stands for the minimum possible number of edges in a k -broadcast graph on n vertices. A k -broadcast graph on n vertices with B k (n) edges is a minimum k -broadcast graph, which is denoted by k -mbg. This thesis presents several new k -mbg's and an improved lower bound on B k (n)

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Shao, Bin
Pagination:xi, 152 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Harutyunyan, Hovhannes
Identification Number:LE 3 C66C67P 2006 S52
ID Code:8801
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:35
Last Modified:13 Jul 2020 20:05
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