Scheduling in broadcast networks

作     者：Hall, NG Liu, WP Sidney, JB 

作者机构：Univ Ottawa Fac Adm Ottawa ON K1N 6N5 Canada Ohio State Univ Columbus OH 43210 USA 

出 版 物：《NETWORKS》 (网络)

年 卷 期：1998年第32卷第4期

页      面：233-253页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：broadcasting scheduling polynomial time algorithm NP-complete 

摘      要：Broadcasting in a communications network has been the subject of many studies in recent years. The studies vary in their assumptions governing the behavior of the network and in their objectives with respect to the network. Almost all the work to date uses the unit transmission time assumption, that is, the message transmission times between all pairs of vertices are equal. In this paper, we investigated the broadcast problem under four more general transmission time assumptions. In addition, four different objective functions were considered, including the minimization of (1) the broadcast time (the maximum time for any vertex to receive the message), (2) the average time to receive the message (both with and without ready times at the vertices), (3) the weighted average time to receive the message, and (4) the cycle time. Of the 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 proved, and heuristics with an attainable constant worst-case performance ratio are provided for two of the problems for which polynomial time algorithms are not found. (C) 1998 John Wiley & Sons, Inc.