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 language | English (US) |
---|---|
Pages (from-to) | 2517-2529 |
Number of pages | 13 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 31 |
Issue number | 4 |
DOIs | |
State | Published - 2017 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Mathematics
Keywords
- Broadcast transmission
- Digital convex polygon
- Dilworth theorem
- Erd-os-Szekeres theorem
- Radio networks