Optimal linear broadcast. (English) Zbl 0774.68014

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.


68M10 Network design and communication in computer systems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI Link