Abstract
We show that for every radio network G = (V, E) and source s ε V, there exists a radio broadcast schedule for G of length Rad(G, s) + O(√Rad(G, s) · log2 n) = O(Rad(G, s) + log4 n), where Rad(G, s) is the radius of the radio network G with respect to the source s. This result improves the previously best-known upper bound of O(Rad(G, s) + log5 n) due to Gaber and Mansour. For graphs with small genus, particularly for planar graphs, we provide an even better upper bound of Rad(G, S) + O(√Rad(G, s) · log n + log3 n) = O(Rad(G, s)+ log3n).
| Original language | English (US) |
|---|---|
| Pages | 222-231 |
| Number of pages | 10 |
| State | Published - 2005 |
| Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |
Other
| Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Country/Territory | United States |
| City | Vancouver, BC |
| Period | 1/23/05 → 1/25/05 |
ASJC Scopus subject areas
- Software
- General Mathematics
Fingerprint
Dive into the research topics of 'Improved schedule for radio broadcast'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver