Login | Register

Improved upper bounds and lower bounds on broadcast function


Improved upper bounds and lower bounds on broadcast function

Li, Zhiyuan (2017) Improved upper bounds and lower bounds on broadcast function. PhD thesis, Concordia University.

This is the latest version of this item.

Text (application/pdf)
Li_PhD_S2018.pdf - Accepted Version
Available under License Spectrum Terms of Access.


Given a graph G=(V,E) and an originator vertex v, broadcasting is an information disseminating process of transmitting a message from vertex v to all vertices of graph G as quickly as possible. A graph G on n vertices is called broadcast graph if the broadcasting from any vertex in the graph can be accomplished in \lceil log n\rceil time. A broadcast graph with the minimum number of edges is called minimum broadcast graph. The number of edges in a minimum broadcast graph on n vertices is denoted by B(n). A long sequence of papers present different techniques to construct broadcast graphs and to obtain upper bounds on B(n). In this thesis, we study the compounding and the vertex addition broadcast graph constructions, which improve the upper bound on B(n). We also present the first nontrivial general lower bound on B(n).

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Li, Zhiyuan
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science
Date:October 2017
Thesis Supervisor(s):Harutyunyan, Hovhannes A.
ID Code:983827
Deposited By: ZHIYUAN LI
Deposited On:05 Jun 2018 14:09
Last Modified:05 Jun 2018 14:09

Available Versions of this Item

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