Low-cost minimum-time line-broadcasting schemes in complete binary trees

Broadcasting is the process of transmitting a message from a member in a ne twork (originator) to all other members. A line-broadcasting scheme allows two members to communicate during one time unit as long as there is a path of lines between them and no link is used in more than one call between two members. Farley [3] showed an algorithm that accomplishes line broadcastin g in any tree on n vertices in minimum time, which is inverted right perpen dicular log(2) n inverted left perpendicular time units. Since the structur e of the tree is unknown in advance, the total number of communication link uses (cost) of his scheme is Theta (n - 1) inverted right perpendicular lo g(2) n inverted left perpendicular. In this paper, we present line-broadcasting schemes for complete binary tre es. The cost of the algorithms is linear in the number of vertices. This an swers a question raised by Fujita and Farley [5]. (C) 2001 John Wiley & Son s, Inc.