MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Funke, Stefan
Laue, Sören		dblp
dblp
Editor(s):
Thomas, Wolfgang
Weil, Pascal		dblp
dblp
Not MPII Editor(s):
Thomas, Wolfgang
Weil, Pascal
BibTeX cite key*:
FL2007
Title, Booktitle
Title*:
Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets
Booktitle*:
STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science
Event, URLs
Conference URL::
http://www-i7.informatik.rwth-aachen.de/stacs07/
Downloading URL:
http://www.springerlink.com/content/x552l41420456648/fulltext.pdf
Event Address*:
Aachen, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
22 February 2007
Event End Date:
24 February 2007
Publisher
Name*:
Springer
URL:
http://www.springer.com
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4393
Number:
Month:
Pages:
272-283
Year*:
2007
VG Wort Pages:
28
ISBN/ISSN:
3-540-70917-6
Sequence Number:
DOI:
10.1007/978-3-540-70918-3_24
Note, Abstract, ©
(LaTeX) Abstract:
We consider the problem of assigning powers to nodes of a wireless network in the plane such that a message from a source node s reaches all other nodes within a bounded number k of transmissions and the total amount of assigned energy is minimized. By showing the existence of a coreset of size we are able to (1 + ε)-approximate the bounded-hop broadcast problem in time linear in n which is a drastic improvement upon the previously best known algorithm.
While actual network deployments often are in a planar setting, the experienced metric for several reasons is typically not exactly of the Euclidean type, but in some sense ’close’. Our algorithm (and others) also work for non-Euclidean metrics provided they exhibit a certain similarity to the Euclidean metric which is known in the literature as bounded doubling dimension. We give a novel characterization of such metrics also pointing out other applications such as space-efficient routing schemes.
This work was supported by the Max Planck Center for Visual Computing and Communication (MPC-VCC) funded by the German Federal Ministry of Education and Research (FKZ 01IMC01).
URL for the Abstract:
http://dx.doi.org/10.1007/978-3-540-70918-3_24
Download
Access Level:
Internal

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



BibTeX Entry:

@INPROCEEDINGS{FL2007,
AUTHOR = {Funke, Stefan and Laue, S{\"o}ren},
 EDITOR = {Thomas, Wolfgang and Weil, Pascal},
 TITLE = {Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets},
 BOOKTITLE = {STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science},
 PUBLISHER = {Springer},
 YEAR = {2007},
 VOLUME = {4393},
 PAGES = {272--283},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Aachen, Germany},
 ISBN = {3-540-70917-6},
 DOI = {10.1007/978-3-540-70918-3_24},
}

Entry last modified by Anja Becker, 02/28/2008
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)
Sören Laue		Created
02/26/2007 14:15:00
Revisions
9.
8.
7.
6.
5.		Editor(s)
Anja Becker
Stefan Funke
Stefan Funke
Uwe Brahm
Uwe Brahm		Edit Dates
25.02.2008 09:24:19
01/18/2008 03:15:46 PM
01/18/2008 02:22:18 PM
2007-07-18 14:45:15
07/07/2007 00:45:06