Stable Approximation Algorithms for Dominating Set and Independent Set

Mark de Berg, Arpan Sadhukhan, Frits Spieksma

We study the Dominating set problem and Independent Set Problem for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is $k$-sta…