Efficient construction of broadcast graphs

A. Averbuch, R. Hollander Shabtai, Y. Roditty

A broadcast graph is a connected graph, $G=(V,E)$, $|V|=n$, in which each vertex can complete broadcasting of one message within at most $t=\lceil \log n\rceil$ time units. A min…