Naslov
Approximating Energy Efficient Paths in Wireless Multi-Hop Networks

Autori
Funke, Stefan ; Matijević, Domagoj ; Sanders, Peter

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003) / - , 2003

Skup
11th Annual European Symposium on Algorithms (ESA 2003)

Mjesto i datum
Budimpešta, Mađarska, 15.09.2003. - 20.09.2003

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
energy efficient paths; wireless multi-hop networks

Sažetak
Given the positions of n sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number k of hops. Known exact algorithms for this problem required \Omega(n \log n) per query pair (p, q). In this paper we relax the exactness requirement and only compute approximate (1+\epsilon) solutions which allows us to guarantee constant query time using linear space and O(n\log n) preprocessing time. The dependence on \epsilon is polynomial in 1/\epsilon. One tool we employed might be of independent interest: For any pair of points (p, q)\in P\subseteq\mathbb{Z}^2 we can report in constant time the cluster pair (A, B) representing (p, q) in a well-separated pair decomposition of P.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA