Fully dynamic maximal independent set with sublinear update time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon · 2018
A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in O(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs?