Faster Dynamic Maximal Independent Set against Adaptive AdversariesResearch Paper
A maximal independent set (MIS) of a graph is a set of vertices, no two adjacent, such that every vertex outside has a neighbour in . It is the basic symmetry-breaking object of parallel and distributed computing. In the fully dynamic setting the graph changes by edge insertions and deletions, and an algorithm must keep an MIS of the current graph…