SCHEDULING IN BROADCAST NETWORKS

Broadcasting in a communications network has been the subject of many studies in recent years. The studies vary in their assumptions governi ng the behavior of the network and in their objectives with respect to the network. Almost all the work to date uses the unit transmission t ime assumption, that is, the message transmission times between all pa irs of vertices are equal. In this paper, we investigated the broadcas t problem under four more general transmission time assumptions. In ad dition, four different objective functions were considered, including the minimization of (1) the broadcast time (the maximum time for any v ertex to receive the message), (2) the average time to receive the mes sage (both with and without ready times at the vertices), (3) the weig hted average time to receive the message, and (4) the cycle time. Of t he 20 problems thus generated, four admit polynomial time algorithms, 15 are (in the equivalent recognition version) unary NP-complete, and the complexity status of one remains open. All these results are prove d, and heuristics with an attainable constant worst-case performance r atio are provided for two of the problems for which polynomial time al gorithms are not found. (C) 1998 John Wiley & Sons, Inc.