We consider multimessage multicasting over the n processor complete (or fully connected) static network when the forwarding of messages is allowed. We present an efficient algorithm that constructs for every degree d problem instance a communication schedule with total communication time at most 2d , where d is the maximum number of messages that each processor may send (or receive). Our algorithm consists of two phases. In the first phase a set of communications are scheduled to be carried out in d time periods in such a way that the resulting problem is a multimessage unicasting problem of degree d . In the second phase we generate a communication schedule for this problem by reducing it to the Makespan Openshop Preemptive Scheduling problem which can be solved in polynomial time. The final schedule is the concatenation of the communication schedules for each of these two phases. For 2 ≤ l ≤ d , we present an algorithm to generate a communication schedule with total communication time at most \lfloor ( 2 ‐ 1/l ) d floor +1 , for problem instances where each processor needs to send messages to at most ld destinations. We also discuss multimessage multicasting for dynamic networks.
