Menu
Set-to-Set Broadcasting is an information distribution problem in a connected graph, \( G = (V, E) \), in which a set of vertices \( A \), called originators, distributes messages to a set of vertices \( B \) called receivers, such that by the end of the broadcasting process each receiver has received the messages of all the originators. This is done by placing a series of calls among the communication lines of the graph. Each call takes place between two adjacent vertices, which share all the messages they have. Gossiping is a special case of set-to-set broadcasting, where \( A = B = V \). We use \( F(A, B, G) \) to denote the length of the shortest sequence of calls that completes the set-to-set broadcast from a set \( A \) of originators to a set \( B \) of receivers, within a connected graph \( G \). \( F(A, B, G) \) is also called the cost of an algorithm. We present bounds on \( F(A, B, G) \) for weighted and for non-weighted graphs.