Title: SET TO SET BROADCASTING IN COMMUNICATION-NETWORKS
Authors: LEE, HM
CHANG, GJ
應用數學系
Department of Applied Mathematics
Keywords: GOSSIP;BROADCAST;COMPLETE GRAPH;TREE;ALGORITHM
Issue Date: 14-Dec-1992
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, we give an exact formula for b(A,B,K(n)) and linear-time algorithms for computing b(A,B,T) and t(A,B,T) of a tree T.
URI: http://hdl.handle.net/11536/3210
ISSN: 0166-218X
Journal: DISCRETE APPLIED MATHEMATICS
Volume: 40
Issue: 3
Begin Page: 411
End Page: 421
Appears in Collections:Articles


Files in This Item:

  1. A1992KF77300010.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.