Efficient broadcast trees for weighted vertices

In this paper, we consider a weighted-vertex model for information dissemination in communication networks. Each node of the network (e.g., a processing machine) is assigned a weight, which represents the delay of the node after receiving data and before sending it to its neighbors. We are interested in the broadcasting problem in which the goal is to disseminate information from one node to all other nodes as quickly as possible. We introduce a simple algorithm for optimal broadcasting from a given node in weighted-vertex trees. We also study the problem of constructing efficient broadcast trees that minimize the required time for broadcasting. We investigate two variants of this problem. First, we show that, given a set of vertices with specified weights, one can construct a tree that connects all vertices and enables broadcasting from any vertex in the optimal time of Θ(logn). Second, given a set of weighted vertices among which one vertex is specified as the originator, we introduce a polynomial algorithm that connects vertices with a tree in which broadcasting from the originator completes in minimum time.