Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling - GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50% throughput in switches).

However, it was recently shown that in networks in which the local pooling conditions are satisfied, GMS achieves 100% throughput. A graph G = (V;E) is said to satisfy the local pooling conditions if for every induced subgraph H of G there exists a function g : V (H) -> [0; 1] such that for every maximal stable set S in H, the sum over all g(v) with v belonging to S is equal to 1.

We first analyse line graphs and give a characterisation of line graphs that satisfy local pooling. Line graphs are of interest since they correspond to the interference graphs of wirless networks under primary interference constraints.

Finally we consider claw-free graphs and give a characterisation of claw-free graphs that satisfy local pooling. This is joint work with Berk Birand (EE, Columbia University), Maria Chudnovsky (IEOR, Columbia University), Paul Seymour (Mathematics, Princeton University), Gil Zussman (EE, Columbia University) and Yori Zwols (IEOR, Columbia University).