Optimal linear broadcast. (English) Zbl 0774.68014

Bitan, Sara; Zaks, Shmuel

J. Algorithms 14, No. 2, 288-315 (1993).

Summary: We investigate the problem of linear broadcast, which is performed in a network in which messages follow linear routes. This is a characteristic of many high-speed networks, in which a special hardware is used for switching. Following, extending, and improving the recent work of C. T. Chou and I. S. Gopal [Linear Broadcast routing, J. Algorithms 10, 490-517 (1989)], we study cases when the switching hardware has various limitations. We present algorithms that compute an optimal broadcast routing for any given number of linear routes. Our main result is an \(O(N)\) algorithm for the general problem of linear broadcast routing, for a tree network of size \(N\), for which an \(O(N^ 2)\) algorithm was given by Chou and Gopal.

MSC:

68M10	Network design and communication in computer systems
68Q25	Analysis of algorithms and problem complexity

Keywords:

linear broadcast; high-speed networks; switching hardware; optimal broadcast routing; tree network