Optimal deterministic broadcasting in known topology radio networks
DR Kowalski, A Pelc - Distributed Computing, 2007 - Springer
Distributed Computing, 2007•Springer
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 O (D+\log^ 2 n), for every n-node …
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 O (D+\log^ 2 n), for every n-node …
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 , 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 BPTIME( holds, the length of a polynomially constructible deterministic broadcast scheme is optimal.
Springer
