Randomized Greedy MIS is Fast at Every NodeResearch Paper
A local computation algorithm answers a query about one part of a global solution (here: is vertex in the maximal independent set?) by inspecting only a small neighbourhood of , so that answers to different queries are consistent with one global solution. Nguyen and Onak (FOCS 2008) simulated the randomized greedy maximal independent set (RGMIS) this…