Approximation Algorithms for Broadcasting in Flower Graphs

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