PERIODIC GOSSIPING ON TREES

In periodic gossip schemes, the calls are periodically repeated accord ing to a proper coloring of the edges of the underlying graph with int egers 1, 2,..., c. One period consists of c consecutive rounds 1, ..., c each containing time-parallel bidirectional calls on all edges with the same color. The problem is to design colorings which minimize the number of periods until gossiping is completed. We present an algorit hm yielding ''reasonable'' colorings for trees, and discuss cases wher e it produces an optimal coloring. For these cases, the periodic gossi p time, i.e. the minimum number of periods can be computed from the al gorithm.