Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update
Options:








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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:

File Attachment Icon
RadioESA03long.ps.gz