We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Optimal Deterministic Broadcasting in Known Topology Radio Networks.
- Authors
Kowalski, Dariusz; Pelc, Andrzej
- Abstract
We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length $$\mathcal{O}(D + \log ^2 n)$$ , for every n-node graph of diameter D, thus improving a result of Gąsieniec et al. (PODC 2005) [17] and solving a problem stated there. Unless the inclusion NP $$\subseteq$$ BPTIME( $$n^{\mathcal{O}(\log \log n)})$$ holds, the length $$\mathcal{O}(D + \log ^2 n)$$ of a polynomially constructible deterministic broadcast scheme is optimal.
- Subjects
OPTICAL communications; RADIO broadcasting; RADIO networks; ALGORITHMS; GRAPH theory; ELECTRIC network topology
- Publication
Distributed Computing, 2007, Vol 19, Issue 3, p185
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-006-0007-8