SOLUTION:
A broadcasting scheme. At time 0 only
contains the message that is
to be broadcast to every vertex. At each time step any vertex that has
received the message is allowed to communicate the message to at most one
of its neighbours.
MEASURE:
The broadcast time, i.e., the time when all vertices have received the
message.
Comment:
Approximable within 2B if the degree of G is bounded by a constant B
[418].
Approximable within
if G is chordal, k-outerplanar
[334].
Approximable within
if G has bounded tree width
[372].
MINIMUM GOSSIP TIME, the extension in which there is a message on
every node and the objective is to minimize the time until every node
has received every message, is approximable within twice the performance
ratio of MINIMUM BROADCAST TIME [418].