We consider multiple message broadcasting in tree networks. The source (con
sidered as the root of the tree) has k messages which have to be broadcast
to all nodes of the tree. In every time unit each node can send one of its
already obtained messages to one of its children. A ii-message broadcasting
scheme prescribes in which time unit a given node should send a message to
which child. It is k-optimal if it achieves the smallest possible time for
broadcasting k messages from the source to all nodes. We give an algorithm
to construct a k-optimal broadcasting scheme for an arbitrary n-node tree.
The time complexity of our algorithm is O(nk), i.e., the best possible, (C
) 1999 Academic Press.