Continuous Delivery Message Dissemination Problems under the Multicasting Communication Mode

T.F. Gonzalez (USA)


Approximation Algorithms, Continuous Delivery, Mes sage Dissemination, Multicasting Communication, For warding.


We consider the continuously delivery message dissemina tion (CDMD) problem under the multicasting communi cation mode over the n processor complete (all links are present and are bi-directional) static networks. This prob lem has been shown to be NP-complete even when all mes sages have the same length. For the CDMD problem we present an ef´Čücient approximation algorithm to construct a message routing schedule with total communication time at most 3.5d, where d is the total length of the messages that each processor may send or receive. Our algorithm takes O(m2 + n log n) time, where n is the number of proces sors and m is the number of messages.

Important Links:

Go Back