Set to set broadcasting in communication networks

Set to set broadcasting in communication networks

0.00 Avg rating0 Votes
Article ID: iaor19931439
Country: Netherlands
Volume: 40
Issue: 3
Start Page Number: 411
End Page Number: 421
Publication Date: Dec 1992
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: graphs, communication
Abstract:

Suppose G=(V,E) is a graph whose vertices represent people and edges represent telephone lines between pairs of people. Each person knows a unique message and is ignorant of the messages of other people at the beginning. These messages are then spread by telephone calls. In each call, two people exchange all information they have so far in exactly one unit of time. Suppose A and B are two nonempty subsets of V. The main purpose of this paper is to study the minimum number b(A,B,G) of telephone calls by which A broadcasts to B; and the minimum time t(A,B,G) such that A broadcasts to B. In particular, the authors give an exact formula for b(A,B,Kn) and linear-time algorithms for computing b(A,B,T) and t(A,B,T) of a tree T.

Reviews

Required fields are marked *. Your email address will not be published.