Login | Register

Optimal broadcasting in treelike graphs

Title:

Optimal broadcasting in treelike graphs

Maraachlian, Edward (2010) Optimal broadcasting in treelike graphs. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
NR71135.pdf - Accepted Version
4MB

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 different classes of graphs which have various similarities to trees. The unicyclic graph is the simplest graph family after trees, it is a connected graph with only one cycle in it. We provide a linear time solution for the broadcast problem in unicyclic graphs. We also studied graphs with increasing number of cycles and complexity and provide again polynomial time solutions. These graph families are: tree of cycles, necklace graphs, and 2-restricted cactus graphs. We also define the fully connected tree graphs and provide a polynomial solution and use these results to obtain polynomial solution for the broadcast problem in tree of cliques and a constant approximation algorithm for the hierarchical tree cluster networks.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Maraachlian, Edward
Pagination:x, 125 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Date:2010
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:979376
Deposited By: Concordia University Library
Deposited On:09 Dec 2014 17:58
Last Modified:18 Jan 2018 17:49
Related URLs:
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