For an experimental comparison, we implemented our two incremental approaches IA and IAW, as well as the static approximation RK, the static exact BA, the dynamic exact algorithms GMB [1]} and KDB [2]} for unweighted graphs and the dynamic exact algorithm NPR [3]} for weighted graphs. We chose to implement NPR because it is the only algorithm with a lower complexity than recomputing from scratch and no experimental results have been provided before. In addition, we also implemented GMB and KDB because they are the ones with the best speedups on unweighted graphs.
We implemented all algorithms in C++, building on the open-source NetworKit framework [4]}.
In all experiments we fix \(\delta \)  to 0.1 while the error bound \(\epsilon \)  varies.
The machine used has 2 x 8 Intel(R) Xeon(R) E5-2680 cores at 2.7 GHz, of which we use only one, and 256 GB RAM. All computations are sequential to make the comparison to previous work more meaningful.
