de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Approximating Energy Efficient Paths in Wireless Multi-hop Networks

MPS-Authors
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;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2C35-7
Abstract
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$.