History

Please fill in your query. A complete syntax description you will find on the General Help page.
Energy-efficient paths in radio networks. (English)
Algorithmica 61, No. 2, 298-319 (2011).
Summary: 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+α})$, 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)\in (P\times P)$ we can report in constant time the cluster pair $(A,B)$ representing $(p,q)$ in a well-separated pair decomposition of $P$.