Heuristics for the Minimum Broadcast Time

Abstract

The problem under study is the Minimum Broadcast Time (MBT). We are given a simple graph and a singleton that owns a message. The goal is to disseminate the message as soon as possible, where the communication takes place between neighboring-nodes in a selective fashion and each forwarding takes one time-slot. The MBT serves as an inspirational problem for the design of delay-sensitive forwarding schemes. Since the problem belongs to the NP-Hard class, the literature offers heuristics, approximation algorithms and exact exponential-time solutions. The contributions of this paper are two-fold. First, an ILP formulation for the problem is provided. Second, a competitive heuristic is developed. A fair comparison between TreeBlock and previous heuristics highlights the effectiveness of our proposal.