CRI Doctoral Forum Lecture, 2008-2009

Abstract:

Efficient operation of wireless networks and switches requiresusing simple (and in some cases distributed) scheduling algorithms. Ingeneral, simple greedy algorithms (known as Greedy Maximal Scheduling -GMS) are guaranteed to achieve only a fraction of the maximum possiblethroughput (e.g., 50% throughput in switches). However, it was recentlyshown that in networks in which the local pooling conditions aresatisfied, GMS achieves 100% throughput. A graph G = (V;E) is said tosatisfy the local pooling conditions if for every induced subgraph H of Gthere exists a function g : V (H) -> [0, 1] such that the sum of all g(v)over all v in S equals 1 for every maximal stable set S in H.

We first analyze line graphs and give a characterization of line graphsthat satisfy local pooling. Line graphs are of interest since theycorrespond to the interference graphs of wireless networks under primaryinterference constraints. Finally we consider claw-free graphs and give acharacterization of claw-free graphs that satisfy local pooling.

This is joint work with Berk Birand, Maria Chudnovsky, Paul Seymour, GilZussman and Yori Zwols.