PDF

Communication Graphs (Joseph G. Peters - Simon Fraser University)

Research on communication graphs dates back to the early days of research in the theory of network communications. These graphs are used to represent the interconnection networks of point-to-point networks. The goal is to find the least costly networks that allow various common communication patterns such as broadcasting and gossiping to complete in minimum time. In the 1980's and early 1990's, there was great interest in the construction of minimum broadcast graphs. With a few notable exceptions, most of the early results were ad hoc constructions. The five-year period, 1988 to 1993, was a sort of golden age for research in this area during which general construction methods replaced ad hoc approaches and researchers gained a deeper understanding of structured communication. Jean-Claude played a central role in these developments. This talk will be an historical survey of the major developments in this research area.