Broadcasting multiple messages in a grid

AbstractThe problem of broadcasting in grid graphs is discussed. Two algorithms for broadcasting m messages in an n×n grid are given. These algorithms require time max(n+52m−1, 2n+2m−4) and time 2n+52m − 4. An algorithm for broadcasting m messages in an n×n×n grid which requires time 3n+103m + 2 is presented. It is conjectured that similar algorithms exist for d-dimensional grids which require time dn + (d2 + 1)/dm + constant