Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Funke, Stefan Matijevic, Domagoj Sanders, Peter dblp dblp dblp
 Editor(s): Di Battista, Giuseppe Zwick, Uri dblp dblp Not MPII Editor(s): Di Battista, Giuseppe Zwick, Uri
 BibTeX cite key*: FMS2003

 Title, Booktitle
 Title*: Approximating Energy Efficient Paths in Wireless Multi-hop Networks RadioESA03long.ps.gz (261.96 KB) Booktitle*: Algorithms - ESA 2003: 11th Annual European Symposium

 Event, URLs
 URL of the conference: http://www.conferences.hu/ALGO2003/ URL for downloading the paper: Event Address*: Budapest, Hungary Language: English Event Date* (no longer used): September 2003 Organization: Event Start Date: 16 September 2003 Event End Date: 19 September 2004

 Publisher
 Name*: Springer URL: http://www.springer.de/ Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2832 Number: Month: September Pages: 230-241 Year*: 2003 VG Wort Pages: 28 ISBN/ISSN: 3-540-20064-9 Sequence Number: DOI:

 (LaTeX) 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$. Keywords: Computational Geometry, Wireless Networks Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: popular Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{FMS2003,
AUTHOR = {Funke, Stefan and Matijevic, Domagoj and Sanders, Peter},
EDITOR = {Di Battista, Giuseppe and Zwick, Uri},
TITLE = {Approximating Energy Efficient Paths in Wireless Multi-hop Networks},
BOOKTITLE = {Algorithms - ESA 2003: 11th Annual European Symposium},
PUBLISHER = {Springer},
YEAR = {2003},
VOLUME = {2832},
PAGES = {230--241},
SERIES = {Lecture Notes in Computer Science},