Bhabak, Puspal (2014) Approximation Algorithms for Broadcasting in Simple Graphs with Intersecting Cycles. PhD thesis, Concordia University.

Text (application/pdf)
1MBThesis_PuspalBhabak.pdf  Accepted Version 
Abstract
Broadcasting is an information dissemination problem in a connected network in which one node, called the originator, must distribute a message to all other nodes
by placing a series of calls along the communication lines of the network. Every time the informed nodes aid the originator in distributing the message. Finding the
minimum broadcast time of any vertex in an arbitrary graph is NPComplete. The problem remains NPComplete even for planar graphs of degree 3 and for a graph
whose vertex set can be partitioned into a clique and an independent set. The best theoretical upper bound gives logarithmic approximation. It has been shown that
the broadcasting problem is NPHard to approximate within a factor of 3ɛ. The polynomial time solvability is shown only for treelike graphs; trees, unicyclic graphs,
tree of cycles, necklace graphs and some graphs where the underlying graph is a clique; such as fully connected trees and tree of cliques. In this thesis we study the
broadcast problem in different classes of graphs where cycles intersect in at least one vertex. First we consider broadcasting in a simple graph where several cycles have common paths and two intersecting vertices, called a kpath graph. We present a constant approximation algorithm to find the broadcast time of an arbitrary kpath graph. We also study the broadcast problem in a simple cactus graph called kcycle
graph where several cycles of arbitrary lengths are connected by a central vertex on one end. We design a constant approximation algorithm to find the broadcast time of an arbitrary kcycle graph.
Next we study the broadcast problem in a hypercube of trees for which we present a 2approximation algorithm for any originator. We provide a linear algorithm to
find the broadcast time in hypercube of trees with one tree. We extend the result for any arbitrary graph whose nodes contain trees and design a linear time constant approximation algorithm where the broadcast scheme in the arbitrary graph is already known.
In Chapter 6 we study broadcasting in Harary graph for which we present an additive approximation which gives 2approximation in the worst case to find the broadcast time in an arbitrary Harary graph. Next for even values of n, we introduce a new graph, called modifiedHarary graph and present a 1additive approximation
algorithm to find the broadcast time. We also show that a modifiedHarary graph is a broadcast graph when k is logarithmic of n.
Finally we consider a diameter broadcast problem where we obtain a lower bound on the broadcast time of the graph which has at least (d+k1 choose d) + 1 vertices that are at a distance d from the originator, where k >= 1.
Divisions:  Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering 

Item Type:  Thesis (PhD) 
Authors:  Bhabak, Puspal 
Institution:  Concordia University 
Degree Name:  Ph. D. 
Program:  Computer Science and Software Engineering 
Date:  12 December 2014 
Thesis Supervisor(s):  Harutyunyan, Hovhannes 
Keywords:  Approximation Algorithm Broadcasting Networks NPHard 
ID Code:  979568 
Deposited By:  PUSPAL BHABAK 
Deposited On:  16 Jul 2015 12:50 
Last Modified:  18 Jan 2018 17:49 
Repository Staff Only: item control page