Breadcrumb

 
 

On K-broadcasting in graphs

Title:

On K-broadcasting in graphs

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

[img]
Preview
PDF - Accepted Version
4Mb

Abstract

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 > Faculty 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
Date:2006
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:8801
Deposited By:Concordia University Libraries
Deposited On:18 Aug 2011 14:35
Last Modified:18 Aug 2011 15:09
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