caa a22 4500 445805447 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9414-0 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9414-0 Energy-Efficient Paths in Radio Networks [Elektronische Daten] [Rene Beier, Stefan Funke, Domagoj Matijević, Peter Sanders] We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights ω(p,q)=|pq|δ+C p, for some constant δ>1 and nonnegative offset costs C p. Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number k of hops. We present an exact algorithm for the important case when δ=2, which requires $\mathcal {O}(kn\log n)$ time per query pair (p,q). For the case of an unrestricted number of hops we describe a family of algorithms with query time $\mathcal {O}(n^{1+\alpha})$, where α>0 can be chosen arbitrarily. If we relax the exactness requirement, we can find an approximate (1+ε) solution in constant time by querying a data structure which has linear size and which can be build in $\mathcal {O}(n\log n)$ time. The dependence on ε is polynomial in 1/ε. One tool we employ might be of independent interest: For any pair of points (p,q)∈(P×P) we can report in constant time the cluster pair (A,B) representing (p,q) in a well-separated pair decomposition of P. Springer Science+Business Media, LLC, 2010 Computational geometry nationallicence Communication networks nationallicence Beier Rene Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut Funke Stefan Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut Matijević Domagoj Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut Sanders Peter Fakultät für Informatik, Universität Karlsruhe, 76128, Karlsruhe, Germany aut Algorithmica Springer-Verlag 61/2(2011-10-01), 298-319 0178-4617 61:2<298 2011 61 453 https://doi.org/10.1007/s00453-010-9414-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9414-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Beier Rene Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Funke Stefan Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Matijević Domagoj Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Sanders Peter Fakultät für Informatik, Universität Karlsruhe, 76128, Karlsruhe, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 298-319 0178-4617 61:2<298 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer