Login | Register

Problems related to broadcasting in graphs


Problems related to broadcasting in graphs

Grigoryan, Hayk (2013) Problems related to broadcasting in graphs. PhD thesis, Concordia University.

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


The data transmission delays become the bottleneck on modern high speed interconnection networks utilized by high performance computing or enterprise data centers. This motivates the study directed towards finding more efficient interconnection topologies as well as more efficient algorithms for information exchange between the nodes of the given network.

Broadcasting is the process of distributing a message
from a node, called the originator, to all other nodes of a communication network. Broadcasting is used as a basic communication primitive by many higher level network operations, which involve a set of nodes in distributed systems. Therefore, it is one the most important operations, which can determine the total efficiency of a given distributed system.

We study interconnection networks via modeling them as graphs. The results described in this work can be used for efficient message routing algorithms in switch based interconnection networks as well as in the choice of the interconnection topologies of such networks.

This thesis is divided into six chapters. Chapter 1 gives a general introduction to the research area and literature overview. Chapter 2 studies the family of graphs for which the broadcast time is equal to the diameter. Chapter 3 studies the routing and broadcasting problem in the Knodel graph. Chapter 4 studies the possible vertex degrees and the possible connections between vertices of different degrees in a broadcast graph. Using this, a new lower bound is obtained on broadcast function. Chapter 5 presents some miscellaneous results. Chapter 6 summarizes the thesis.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Grigoryan, Hayk
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Date:6 September 2013
Thesis Supervisor(s):Hovhannes, Harutyunyan
ID Code:977773
Deposited On:13 Jan 2014 14:40
Last Modified:18 Jan 2018 17:45
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