de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### Approximating Energy Efficient Paths in Wireless Multi-hop Networks

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44464

Funke,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45000

Matijevic,  Domagoj
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45344

Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Funke, S., Matijevic, D., & Sanders, P. (2003). Approximating Energy Efficient Paths in Wireless Multi-hop Networks. In Algorithms - ESA 2003: 11th Annual European Symposium (pp. 230-241). Berlin, Germany: Springer.

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 require approximate $(1+\epsilon)$ solutions which allows us to derive schemes which 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 used might be of independent interest: For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$ report in constant time the cluster pair $(A,B)$ representing $(p,q)$ in a well-separated pair decomposition of $P$.