Campus Event Calendar
Event Entry
New for: D1
What and Who
An O(1)-Approximation Algorithm for the k-Set Broadcast Problem
Rouven Naujoks
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 4 July 2008
13:30
30 Minutes
E1 4
D1 Rotunde
Saarbrücken
Warning: New Room!
Abstract
Broadcasting a message from a given source node to all other nodes is a fundamental task during the operation of a wireless network. In
many application scenarios the network nodes have only a limited energy supply, hence minimizing the energy consumption of any communication task prolongs the lifetime of the network
In this talk we consider a constrained broadcast operation, where a
source node wants to send a message to all other nodes in the network
but at most k nodes are allowed to participate actively.
For the case of network nodes embedded in the Euclidean plane we provide an O(1)-approximation algorithm with running time linear in the number of nodes and polynomial in k.
Contact
Rouven Naujoks
--email hidden
passcode not visible
logged in users only
Rouven Naujoks, 07/04/2008 12:34
Rouven Naujoks, 07/03/2008 10:42 -- Created document.
Rouven Naujoks, 07/03/2008 10:42 -- Created document.