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 efficient 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
