Report ID
1997-24
Report Authors
Teofilo F. Gonzalez
Report Date
Abstract
We consider Multimessage Multicasting over the $n$ processor complete (or fullyconnected) static network ($MM_{C}$) when the Forwarding of messages isallowed. We present an efficient algorithm that constructs for every degree$d$ problem instance a communication schedule with total communication time atmost $2d$, where $d$ is the maximum number of messages that each processor maysend (receive). Our algorithm consists of two phases. In the first phase aset of communications are scheduled to be carried out in $d$ time periods insuch a way that the resulting problem is a multimessage unicasting problem ofdegree $d$. In the second phase we generate a communication schedule for thisproblem by reducing it to the Makespan Openshop Preemptive Scheduling problemwhich can be solved in polynomial time. The final schedule is theconcatenation of the communication schedules for each of these two phases. For$2 \\le l \\le d$ we present an algorithm to generate a communication schedulewith total communication time at most $\\lfloor ( 2 - \\frac{1}{l} ) d \\rfloor+1$, for problem instances where each processor needs to send messages to atmost $ld$ destinations.
Document
1997-24.ps261.79 KB