@inbook{e38a1ce99ef34b96b33247f981f9b07c,
title = "Centralized deterministic broadcasting in undirected multi-hop radio networks",
abstract = "We consider centralized deterministic broadcasting in radio networks. The aim is to design a polynomial algorithm, which, given a graph G, produces a fast broadcasting scheme in the radio network represented by G. The problem of finding an optimal broadcasting scheme for a given graph is NP-hard, hence we can only hope for a good approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcasting scheme working in time O(D log n + log2 n), for every n-node graph of diameter D. It has been proved recently [15, 16] that a better order of magnitude of broadcasting time is impossible unless NP ⊆ BPTIME(no(log log n)). In terms of approximation ratio, we have a O(log(n/D))-approximation algorithm for the radio broadcast problem, whenever D = Ω(log n).",
author = "Kowalski, {Dariusz R.} and Andrzej Pelc",
year = "2004",
month = jan,
day = "1",
doi = "10.1007/978-3-540-27821-4_16",
language = "English (US)",
isbn = "3540228942",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "171--182",
editor = "Klaus Jansen and Sanjeev Khanna and Rolim, {Jose D. P.} and Dana Ron",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
}