LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » 链接 » 巴黎六大计算机科学实验室日志


Connectivity of Bluetooth Graphs

报告人 : Nicolas BROUTIN (Inria Paris-Rocquencourt)
One of the main models for wireless networks is the random geometric graph. In this model, the graph gets connected with high probability only when the average degree is of the order of the logarithm of the size. Although it is not enourmous, it still raises the question of the scalability. Other models (irrigation graphs or Bluetooth graphs) have been devised that sparsify the graph using a local rule and hope that it remains connected. We prove tight threshold for the number of edges necessary for connectivity in this model, showing that the average degree must in particular tend to infinity to expect connectivity.
This is joint work with L. Devroye, N. Fraiman and G. Lugosi.
emilie.coupechoux (at)
 Mentions légales
网站导航 |