Nordic Journal of Computing Bibliography

Teofilo F. Gonzalez. Bounded Fan-Out Multimessage Multicasting. Nordic Journal of Computing, 5(3):196-213, Fall 1998.

We consider Multimessage Multicasting over the n processor complete (or fully connected) static network (MMC}). We present a fast approximation algorithm with an improved approximation bound for problem instances with small fan-out (maximum number of processors receiving any given message), but arbitrary degree d, where d is the maximum number of messages that each processor may send or receive. These problem instances are the ones that arise in practice, since the fan-out restriction is imposed by the applications and the number of processors available in commercial systems.

Our algorithm is centralized and requires all the communication information ahead of time. Applications where this information is available include iterative algorithms for solving linear equations and most dynamic programming procedures. The Meiko CS-2 machine as well as other computer systems whose processors communicate via dynamic networks will also benefit from our results at the expense of doubling the number of communication phases.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; C.1.4 [Processor Architectures]: ; G.2.2 [Discrete Mathematics]: Graph Theory; C.2.1 [Computer-Communication Networks]: Network Architecture and Design; G.1.3 [Numerical Analysis]: Numerical Linear Algebra

Additional Key Words and Phrases: approximation algorithms, multimessage multicasting, dynamic networks, parallel iterative methods, generalized edge coloring

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database