Titlebook: Structural Information and Communication Complexity; 19th International C Guy Even,Magnús M. Halldórsson Conference proceedings 2012 Spring

渗透

Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position,m spanning tree of . has maximum interference .(log.) with high probability. We extend this bound to a general class of communication graphs over a broad set of probability distributions. We present a local algorithm that constructs a graph from this class; this is the first local algorithm to provi

连接

放逐

Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model,lity, where . is the network diameter, . is the number of messages whose broadcasts overlap with ., and . is the number of nodes in the network. We also study the lower bound for randomized distributed multiple-message broadcast protocols. In particular, we prove that any uniform randomized algorith