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

RSS

Connectivity of Bluetooth Graphs


2013-3-28
报告人 : 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) nulllip6.fr
 Mentions légales
网站导航 |