  Computing the size of maximum independent sets is a NP-hard problem for fixed
graphs. Characterizing and designing efficient algorithms to estimate this
independence number for random graphs are notoriously difficult and still
largely open issues. In a companion paper, we showed that a low complexity
degree-greedy exploration is actually asymptotically optimal on a large class
of sparse random graphs. Encouraged by this result, we present and study two
variants of sequential exploration algorithms: static and dynamic degree-aware
explorations. We derive hydrodynamic limits for both of them, which in turn
allow us to compute the size of the resulting independent set. Whereas the
former is simpler to compute, the latter may be used to arbitrarily approximate
the degree-greedy algorithm. Both can be implemented in a distributed manner.
The corresponding hydrodynamic limits constitute an efficient method to compute
or bound the independence number for a large class of sparse random graphs. As
an application, we then show how our method may be used to estimate the
capacity of a large 802.11-based wireless network. We finally consider further
indicators such as the fairness of the resulting configuration, and show how an
unexpected trade-off between fairness and capacity can be achieved.
