Improved schedule for radio broadcast

Michael Elkin; Guy Kortsarz

Improved schedule for radio broadcast

Michael Elkin, Guy Kortsarz

Rutgers Camden, Computer Science

Research output: Contribution to conference › Paper › peer-review

42 Scopus citations

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) · log² n) = O(Rad(G, s) + log⁴ 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) + log⁵ 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 + log³ n) = O(Rad(G, s)+ log³n).

Original language	English (US)
Pages	222-231
Number of pages	10
State	Published - Jul 1 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	United States
City	Vancouver, BC
Period	1/23/05 → 1/25/05

All Science Journal Classification (ASJC) codes

Software
Mathematics(all)

Access to Document

Fingerprint Dive into the research topics of 'Improved schedule for radio broadcast'. Together they form a unique fingerprint.

Cite this

@conference{69c3bd3ba805417f8481a892c6a59901,

title = "Improved schedule for radio broadcast",

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).",

author = "Michael Elkin and Guy Kortsarz",

year = "2005",

month = jul,

day = "1",

language = "English (US)",

pages = "222--231",

note = "Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-2005 Through 25-01-2005",

}

TY - CONF

T1 - Improved schedule for radio broadcast

AU - Elkin, Michael

AU - Kortsarz, Guy

PY - 2005/7/1

Y1 - 2005/7/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=20744454900&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20744454900&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:20744454900

SP - 222

EP - 231

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -