Bounding Algorithms for the Minimum Broadcast Time Problem

Abstract

The minimum broadcast time problem concerns information dissemination in a graph given a set of initially informed nodes called source nodes. Each informed node can only inform at most one of its neighbors each time step. The minimum broadcast time problem asks for the minimum number of time steps needed until all nodes are informed. It is an NP-hard problem for general graphs. This thesis builds on previous Integer Linear Programs (ILP) for constructing lower bounds. A new approach, adding time- step indexed variables is proposed. Computational properties are proved for this lower bound model and relaxations of it. In addition, we present a branch-and-bound algorithm using such an ILP model, where an upper-bound heuristic is constructed using the ILP optimal solution. Two sets of experiments are conducted. The first demonstrates our lower bound’s superiority over other lower-bounding algorithms in several instances. The second set of experiments compares our branch-and-bound to current leading algorithms with the conclusion that our branch-and-bound algorithm is unable to beat a commercial solver applied to an integer programming formulation from the literature.