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
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to