Efficiency of dissemination of information in one-way and two-way communication networks
Frank Harary, Allen J. Schwenk · Systems Research and Behavioral Science · 1974
The setting of the problem is that each of n people knows a unique item of information and everyone wants to know everything. It is also given that certain pairs can contact each other directly and the remaining pairs cannot, that is, a specified communication network is at hand. The question is who should talk with whom and in what order so that all the information is exchanged most efficiently, using a minimum number of contacts. The mathematical model for this two-way communication problem is that of a connected graph G. When G contains a quadrilateral, a most efficient method for this purpose is developed which requires only 2n - 4 contacts. Otherwise, we present a procedure using just one more contact, 2n - 3. For one-way communications, a strongly connected directed graph provides the appropriate model and in this apparently much more restricted situation, we show that just one further contact, namely 2n - 2, will serve. Incidentally, this handles the common symbol problem, which is equivalent. Finally, we examine circumstances under which every permitted contact can be used in achieving a maximally efficient solution.