Abstract

This thesis is a study on the broadcasting problem in various graph topologies containing intersecting cliques. Broadcasting, is a fundamental message dissemination problem in interconnection networks, requiring an informed originator node to distribute information to all network nodes efficiently. Determination of the broadcast time of any node in an arbitrary network is known to be NP-hard. Polynomial time solutions are known only for a few network topologies. There also exist various heuristic and approximation algorithms for different network topologies. The work in this thesis addresses this challenge through the development and enhancement of algorithms tailored to specific graph structures such as windmill graphs, star of cliques, path-connected cliques, fully connected cliques, and block graphs.

Chapter 3 studies the broadcasting problem in windmill graphs and stars of cliques. A windmill graph is defined on $n$ vertices containing $k$ cliques of size $l$, and a universal vertex. We present a constant time method introduced for determining the broadcast time of an arbitrary node in any windmill graph. We also introduce \textit{Star of Cliques}, a generalization of the Windmill graph composed of cliques with arbitrary sizes. We study the importance of unaddressed vertices in an optimal scheme for star of cliques and show the use of binary representations to track unaddressed vertices. We present an $O(n \cdot \log n)$ algorithm to find the broadcast time of any vertex in an arbitrary star of cliques and discuss the optimality of our algorithm.

Chapter 4 delves into broadcasting within families of block graphs, such as path-connected cliques and fully connected cliques. Every biconnected component in a block graph is a clique. We study broadcasting in block graphs with two cliques, present a constant time method to calculate the broadcast time for an arbitrary path-connected cliques graph, and discuss a $O(n \log\log s_{center})$ method to determine the broadcast time for arbitrary fully connected cliques, where $s_{center}$ is the number of vertices in the central clique of the graph.