An efficient heuristic for broadcasting in networks

In this paper, we present a heuristic for broadcasting in arbitrary networks. This heuristic generates optimal broadcast time for ring, tree and grid graphs when the originator is a corner vertex. In practice, the new heuristic outperforms the best known broadcast algorithms for three different network models. The time complexity of one round of the heuristic is O(|E|), where |E| stand for the number of edges of the network.