Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Bounded-hop Energy-efficient Broadcast in Low-dimensional Metrics Via Coresets

Funke, S., & Laue, S. (2007). Bounded-hop Energy-efficient Broadcast in Low-dimensional Metrics Via Coresets. In W. Thomas, & P. Weil (Eds.), STACS 2007 (pp. 272-283). Berlin: Springer. doi:10.1007/978-3-540-70918-3_24.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
FL2007.pdf (beliebiger Volltext), 5KB
 
Datei-Permalink:
-
Name:
FL2007.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
BroadcastDD.ps (beliebiger Volltext), 5KB
 
Datei-Permalink:
-
Name:
BroadcastDD.ps
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/postscript
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Funke, Stefan1, Autor           
Laue, Sören1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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).

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2008-02-2820072007
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 356733
DOI: 10.1007/978-3-540-70918-3_24
Anderer: Local-ID: C12573CC004A8E26-7CAF38D9D2C68FA1C125728E0048C8FF-FL2007
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 24th Annual Symposium on Theoretical Aspects of Computer Science
Veranstaltungsort: Aachen, Germany
Start-/Enddatum: 2007-02-22 - 2007-02-24

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: STACS 2007
  Kurztitel : STACS 2007
  Untertitel : 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Proceedings
Genre der Quelle: Konferenzband
 Urheber:
Thomas, Wolfgang1, Herausgeber
Weil, Pascal1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 272 - 283 Identifikator: ISBN: 3-540-70917-6

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 4393 Artikelnummer: - Start- / Endseite: - Identifikator: ISSN: 0302-9743