Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica - D(S)I
via Salaria 113, III piano
Aula Seminari

Abstract:
In the study of wireless networks, the following problem is both natural and of great interest (practical and otherwise). If $n$ devices are distributed in some region at random, and links can be established between any two nodes within distance $r$, what is a good strategy for connecting nodes, in order to obtain good connectivity properties of the resulting global network? We will show the following: if each node connects to c>1 nodes chosen uniformly at random among those within distance r, then the network is connected with high probability. This has several nice consequences. In particular it leads to real Bluetooth protocols for scatternet formation that outperform existing approaches, and it shows how spanning sparse networks of very low average degree can be computed distributively in constant-time.

Joint work with Devdatt Dubhashi and Olle Haeggstroem.