Abstract

Broadcasting is a fundamental information dissemination primitive in interconnection networks, where a message is passed from one node to all other nodes in the network. Following the increasing interest in interconnection networks, extensive research was dedicated to broadcasting. Two main research goals of this area are finding inexpensive network structures that maintain efficient broadcasting and finding the broadcast time of a given network topology. In the scope of this study, we will mainly focus on determining the broadcast time of a given network. The broadcast time problem on an arbitrary network is known to be NP-hard. We consider this problem on different network topologies and settings.

We begin by studying the broadcast time problem on split graphs. First, we introduce a tight polynomial-time constant approximation algorithm for broadcasting on split graphs. Then, we study some important characteristics of an optimal broadcast scheme on split graphs and design a strategy for generating optimal broadcast schemes. We apply our findings to devise an efficient broadcasting heuristic on split graphs and on natural generalization of split graphs, called (k,l)-graphs.

Next, we study broadcasting on graphs that comprise some recursive structures. We introduce an exact polynomial-time algorithm on closed chains of rings. A closed chain of rings is a sequence of cycles, where every two consecutive cycles, and the first and the last cycles, share a common vertex. Additionally, we initiate a novel direction to designing broadcasting algorithms on recursively defined graphs. We provide a theoretical foundation for future broadcasting research, as well as discuss several practical applications of the approach we introduce.

Last, we study the problem on k-path graphs, one of the simpler graph families with intersecting cycles. To better understand the challenges of broadcasting on arbitrary graphs, families with intersecting cycles are crucial to study. We improve the current best approximation ratio for broadcasting on k-path graphs by a multiplicative factor of two. Further, we propose a new optimization problem called 3-List-Sub, helping us to design an optimal broadcasting algorithm on restricted k-path graphs which was unsolved to date.