×

An efficient vertex addition method for broadcast networks. (English) Zbl 1184.68033

Summary: Broadcasting is a basic problem of communication in usual networks. Many papers have investigated the construction of minimum broadcast networks, the cheapest possible broadcast network architecture (having the fewest communication lines), in which broadcasting can be accomplished as fast as theoretically possible from any vertex. Since this problem is very difficult, numerous papers have investigated ways to construct sparse networks in which broadcasting can be completed in minimum time from any originator. We introduce an efficient vertex addition method that allows us to construct sparse networks and improve the best known upper bounds on the broadcast function \(B(n)\) for many odd values of \(n\). We also give the exact value of \(B(127)\).

MSC:

68M10 Network design and communication in computer systems
Full Text: DOI