Broadcasting problem

Материал из WikiGrapp
Перейти к:навигация, поиск

Broadcasting problemпроблема широковещания.

The broadcasting problem is the problem of information dissemination described in a group of individuals connected by a communication network. In broadcasting, one node knows a piece of information and needs to transmit it to everyone else. This is achieved by placing communication calls over the communication lines of the network. It is assumed that a node can communicate with at most one of its neighbors at any given time, and communication between two nodes takes one unit of time. This model implies that we will deal with connected graphs without loops and multiple edges to model the communication network. Note also that, depending on their cases, we will either consider a half-duplex or a full-duplex model. In the letter, when communication takes place along a communication line, the information flows in both directions, while in the former only one direction is allowed. Hence, in the half-duplex model, we will deal with directed graphs, while we will consider undirected graphs in the full-duplex model.

See also


  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.