Login | Register

Broadcasting in highly connected graphs


Broadcasting in highly connected graphs

Khanlari, Aram (2023) Broadcasting in highly connected graphs. Masters thesis, Concordia University.

[thumbnail of Khanlari_MCompSc_F2023.pdf]
Text (application/pdf)
Khanlari_MCompSc_F2023.pdf - Accepted Version
Available under License Spectrum Terms of Access.


Throughout history, spreading information has been an important task. With computer networks expanding, fast and reliable dissemination of messages became a problem of interest for computer scientists. Broadcasting is one category of information dissemination that transmits a message from a single originator to all members of the network. In the past five decades the problem has been studied by many researchers and all have come to demonstrate that despite its easy definition, the problem of broadcasting does not have trivial properties and symmetries. For general graphs, and even for some very restricted classes of graphs, the question of finding the broadcast time and scheme remains NP-hard. This work uses graph theoretical concepts to explore mathematical bounds on how fast information can be broadcast in a network. The connectivity of a graph is a measure to assess how separable the graph is, or in other words how many machines in a network will have to fail to disrupt communication between all machines in the network.

We initiate the study of finding upper bounds on broadcast time b(G) in highly connected graphs. In particular, we give upper bounds on b(G) for k-connected graphs and graphs with a large minimum degree.

We explore 2-connected (biconnected) graphs and broadcasting in them. Using Whitney's open ear decomposition in an inductive proof we propose broadcast schemes that achieve an upper bound of ceil(n/2) for classical broadcasting as well as similar bounds for multiple originators. Exploring further, we use a matching-based approach to prove an upper bound of ceil(log(k)) + ceil(n/k) - 1 for all k-connected graphs. For many infinite families of graphs, these bounds are tight.

Discussion of broadcasting in highly connected graphs leads to an exploration of dependence between the minimum degree in the graph and the broadcast time of the latter. By using similar techniques and arguments we show that if all vertices of the graph are neighboring linear numbers of vertices, then information dissemination in the graph can be achieved in ceil(log(n)) + C time.

To the best of our knowledge, the bounds presented in our work are a novelty. Methods and questions proposed in this thesis open new pathways for research in broadcasting.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Khanlari, Aram
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:26 July 2023
Thesis Supervisor(s):Harutyunyan, Hovhannes A.
Keywords:Broadcasting, 2-connected graphs, k-connected graphs, minimum degree, diameter
ID Code:992648
Deposited By: Aram Khanlari
Deposited On:14 Nov 2023 20:35
Last Modified:14 Nov 2023 20:35
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