Greedy sequential maximal independent set and matching are parallel on average.

Guy E. Blelloch, Jeremy T. Fineman, Julian Shun

Browse the full SPAA paper archive.