An algorithm for constructing minimal c-broadcast networks

c-Broadcasting is a special process to disseminate a single message, originated at any node in a network, to all other nodes of the network by letting each informed node transmit the message to at most c neighbors simultaneously, A minimal c-broadcast network (c-mbn) is a communication network in which c-broadcasting can be completed in minimum time from any node. An optimal c-broadcast network (c-obn) is a c-mbn with the smallest number of edges. Previous studies showed that c-obn's are extremely difficult to find. A network compounding algorithm is proposed to construct sparse c-mbn's with n(1)n(2) - i nodes by connecting a subset of nodes from several copies of a c-mbn with nl nodes using the structure of another c-mbn with nz nodes, such that n(1) greater than or equal to 1 and 0 less than or equal to i < n(2), satisfying [log(c+1)(n(1)n(2) - i)] = [log(c+1) n(1)] + [log(c+1)n2]. Computational results are also provided. (C) 2001 John Wiley & Sons, Inc.