On broadcasting multiple messages in a d-dimensional grid

AbstractAn algorithm for broadcasting multiple messages on a d-dimensional grid (d ⩾ 3) starting from the (1, 1, …, 1) corner is presented. The algorithm has a complexity of d(n + m − 2), where m is the number of messages transmitted and n is the number of points in each dimension. This answers a conjecture that appears in Van Scoy and Brookes (1994), namely, that the time required for broadcasting m messages over this d-dimensional grid is dn + ((d2 + 1)d)m + k, k being a constant.Then, we discuss the case where the starting point (for transmitting the message) is arbitrary