MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.conferences.hu/ALGO2003/
Downloading URL:
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:
Note, Abstract, ©
(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},
 ADDRESS = {Budapest, Hungary},
 MONTH = {September},
 ISBN = {3-540-20064-9},
}

Entry last modified by Domagoj Matijevic, 02/24/2005
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Domagoj Matijevic		Created
01/08/2004 01:10:12 PM
Revisions
6.
5.
4.
3.
2.		Editor(s)
Domagoj Matijevic
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
02/24/2005 02:52:40 PM
15.06.2004 17:50:53
14.06.2004 08:30:35
14.06.2004 08:26:49
11.06.2004 16:47:30

File Attachment Icon
RadioESA03long.ps.gz