Bitan, Sara; Zaks, Shmuel Optimal linear broadcast. (English) Zbl 0774.68014 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. Cited in 2 Documents 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 PDF BibTeX XML Cite \textit{S. Bitan} and \textit{S. Zaks}, J. Algorithms 14, No. 2, 288--315 (1993; Zbl 0774.68014) Full Text: DOI