Broadcast transmission to prioritizing receivers

Noga Alon, Guy Rutenberg

Research output: Contribution to journalArticle

Abstract

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
Volume31
Issue number4
DOIs
StatePublished - Jan 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

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

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

  • Cite this