Login | Register

Heuristic Algorithms For Broadcasting In Cactus Graphs

Title:

Heuristic Algorithms For Broadcasting In Cactus Graphs

Conlan, Neil (2017) Heuristic Algorithms For Broadcasting In Cactus Graphs. Masters thesis, Concordia University.

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

Abstract

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Once informed, the nodes aid the originator in distributing the message. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The problem is solved polynomially only for a few classes of graphs. In this thesis, we study the broadcast problem in a class of graph called a Cactus Graph. A cactus graph is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle. We review broadcasting on subclasses of cactus graphs such as, the unicyclic graphs, necklace graphs, k-cycle graphs, 2-restricted cactus graphs and k-restricted cactus graphs. We then provide four heuristic algorithms that solves broadcasting on a k-cycle graph. A k-cycle graph is a collection of k cycles of arbitrary lengths all connected to a central vertex. Finally, we run simulations of these heuristic algorithms on different sized k-cycle graphs to compare and discuss the results.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Conlan, Neil
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:30 April 2017
Thesis Supervisor(s):Maraachlian, Edward and Harutyunyan, Hovhannes
ID Code:982510
Deposited By: NEIL CONLAN
Deposited On:09 Jun 2017 15:00
Last Modified:30 Apr 2019 00:00
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