Multimessage multicasting: complexity and approximations

The author considers the multimessage multicasting problem for complete static networks. The author presents problem instances that require d² time to transmit all their messages, where d is the maximum number of messages that each processor may send (receive). The author shows that when messages have fan-out k=1, the problem is polynomially solvable, and becomes NP-complete when k⩾2. The author presents an algorithm to generate schedules with total communication time 2d-1 when k=2. The author presents an efficient algorithm with an approximation bound of qd+k¹q/(d-1), for any integer k>q⩾2. The algorithms are centralized and require all the communication information ahead of time. The author discusses several applications when all of this information is available. By doubling the number of communication phases, the results apply to the Meiko CS-2 machine and in general to dynamic networks