Next: MINIMUM K-CENTER Up: Miscellaneous Previous: Miscellaneous Index

### MINIMUM BROADCAST TIME

- INSTANCE: Graph and a source node .

- SOLUTION: A broadcasting scheme. At time 0 only v0 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.

- Good News: Approximable within [396].

- Comment: Approximable within 2B if the degree of G is bounded by a constant B [396]. Approximable within if G is chordal, k-outerplanar [319]. Approximable within if G has bounded tree width [352].

  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 [396].

- Garey and Johnson: ND49

Next: MINIMUM K-CENTER Up: Miscellaneous Previous: Miscellaneous Index