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