Login | Register

Approximation Algorithms for Broadcasting in Flower Graphs


Approximation Algorithms for Broadcasting in Flower Graphs

Ehresmann, Anne-Laure (2021) Approximation Algorithms for Broadcasting in Flower Graphs. Masters thesis, Concordia University.

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


Over the last century, telecommunication networks have become the nervous system of our society. As data is generated and stored on varied nodes, effective communication is imperative to ensure efficient use of the network. Our ever-growing reliance on these increasingly large and complex networks make ineffective communication strategies evermore apparent.

Broadcasting is a fundamental information-dissemination problem which models communication across a connected graph in the following manner: a single vertex, the originator, seeks to pass some message along to all other vertices in the graph. In general, research on broadcasting can be grouped in roughly two categories: Firstly, given some particular graph and some particular vertex chosen to be originator, what is a broadcast scheme that informs the entire graph in the minimum time possible? Secondly, given some number of nodes, how can we arrange them in a particular network topology such that we can achieve minimal broadcast time from any vertex? This thesis focuses on problems of the first category. Finding the minimum broadcast time of any vertex in an arbitrary graph is NP-Complete, but efficient algorithms have been found for particular graph families. In particular, polynomial time algorithms have been found for trees and some tree-like graphs: unicyclic graphs, tree of cycles. Such algorithms have also been found for some graphs with no intersecting cliques, such as fully connected trees and trees of cliques. Finally, graphs containing cycles with particular restrictions were also studied, and efficient algorithms for necklace graphs and k-restricted cactus graphs were also found. The question still stands however, of whether these restrictions may be too conservative, and that efficient algorithms exist on broader classes of graphs. In particular, significant research has been made towards finding an efficient broadcasting algorithm on cactus graphs, which has not been found so far.

This thesis studies the broadcasting problem on Flower graphs, which capture the difficulty of cactus graphs in a simple graph family. Flower graphs, or k-cycle graphs, are graphs composed of k cycles all joined on a single central vertex v_c. The contributions of this thesis for broadcasting on flower graphs is two-fold: it first improves the approximation ratio for broadcasting on flower graphs. It then provides a heuristic which performs significantly better in practice than the current best heuristic. We also demonstrate that our heuristic finds the optimal broadcast time for particular subcases of flower graphs.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Ehresmann, Anne-Laure
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:22 August 2021
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:988975
Deposited By: Anne-Laure Ehresmann
Deposited On:29 Nov 2021 16:41
Last Modified:29 Nov 2021 16:41
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