Efficient distributed graph algorithms in wireless networks
Graphs, Hypergraphs, and Computing
06 March 15:30 - 16:30
Dariusz Kowalski - University of Liverpool
The physical nature of wireless communication causes various problems in the implementation of algorithms, in particular, graph algorithms that are often helpful as building blocks for efficient communication and computation. During the lecture I will introduce popular models of wireless networks based on the Signal-to-Interference-and-Noise-Ratio (SINR) physical rule of receiving messages, together with associated geometric and combinatorial aspects. I will show few examples of particularly useful objects, such as trees, independent sets and (connected) dominating sets, and efficient distributed algorithms for their constructions in the SINR models. The talk will be concluded by a number of more complex scenarios for which efficient distributed algorithms are not known.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU