Large Independent Sets in Line of Sight Networks

15^th February 2018, 14:00
Michele Zito

Abstract

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles restricting node visibility. For fixed positive integer d, and positive integer ?, a graph G = (V, E) is a (d-dimensional) LoS network with range parameter ? if it can be embedded in a cube of side size n of the d-dimensional integer grid so that each pair of vertices in V are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than ?. The talk focuses on the Maximum Independent Set (MIS) problem. The problem is obviously easy on grids but it becomes much more interesting in general LoS networks. I will present a gentle (low on maths, high on pictures) introduction to the main known results on this problem in LoS networks, highlighting techniques and open problems.

[THIS IS JOINT WORK WITH PAVAN SANGHA AND PRUDENCE WONG]