A Broadcasting Heuristic for Hypercube of Trees

Broadcasting is the process of dissemination of information in a network where a particular message is sent starting from an originator. The ultimate objective is to inform all entities of the network as soon as possible. Besides, the theory of broadcasting has been used in a wide range of applications. Although the problem has been proven to be NP-Complete for an arbitrary graph, it is tractable for a few families of networks, such as Hypercubes, one of the most successful large-scale parallel architectures. In this paper, we propose a new heuristic for broadcasting in a hypercube of trees in which each vertex of the hypercube could be the root of a tree. Not only does this heuristic have the same approximation ratio as the best-known algorithm and provide a good theoretical bound, but our numerical results also show its superiority in most experiments. Our heuristic is able to outperform the current upper bound in up to 90% of the situations, resulting in an average speedup of 30%. Most importantly, our results illustrate that it can maintain its performance even if the size of the network grows, which makes the proposed heuristic practically useful.