Broadcast transmission to prioritizing receivers

Noga Alon, Guy Rutenberg

Research output: Contribution to journalArticlepeer-review


We consider a broadcast model involving multiple transmitters and receivers. Transmission is performed in rounds, where in each round any transmitter is allowed to broadcast a single message, and each receiver can receive only a single broadcast message, determined by a priority permutation over the transmitters. The message received by receiver R in a given transmission round is the one sent by the first transmitter among all those broadcasting in that round according to the permutation of R. In our model, each pair of transmitter and receiver has a unique message which the transmitter has to send to the receiver. We prove upper and lower bounds on the minimal number of rounds needed for transmitting all the messages to their respective receivers. We also consider the case where the priority permutations are determined geometrically.

Original languageEnglish (US)
Pages (from-to)2517-2529
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Issue number4
StatePublished - 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


  • Broadcast transmission
  • Digital convex polygon
  • Dilworth theorem
  • Erd-os-Szekeres theorem
  • Radio networks


Dive into the research topics of 'Broadcast transmission to prioritizing receivers'. Together they form a unique fingerprint.

Cite this