Broadcasting is one of the fundamental information dissemination primitives in interconnection networks, where a message is passed from one node (called originator) 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 for well-known and widely used network topologies. In the scope of this study, we will mainly focus on determining the broadcast time and nearoptimal broadcasting schemes in networks. 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. In this study, we consider the broadcast time problem on graphs that comprise some recursive structures. We initiate a novel direction to designing broadcasting algorithms on recursively defined graphs. We provide a theoretical foundation for future broadcasting studies, as well as discuss several practical applications of the approach we introduce.

Broadcasting is an information dissemination problem in a connected graph in which one vertex, called the originator, must distribute a message to all other vertices by placing a series of calls along the edges of the graph. Every time the informed vertices aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. We designed an efficient heuristic, which improves the results of existing heuristics in most cases. Extensive simulations show that our new heuristic outperforms the existing ones for most of the commonly used interconnection networks in some network models generated by network simulator ns-2.