The fastest existing method for computing BC is due to Brandes [1]}. It
requires \(\Theta (nm)\)  operations for unweighted graphs and \(\Theta (nm+n^{2}\log n)\) 
for graphs with positive edge weights.
This time complexity is prohibitive for large-scale graphs with millions of edges, though.
Recent years have seen the publication of several ap proximation algorithms
that aim to reduce the computational effort, while finding BC values
that are as close as possible to the exact
ones. Good results have been obtained in this regard; in particular,
a recent algorithm by Riondato and Kornaropoulos (RK) [2]} gives probabilistic guarantees on the quality of the approximation, and we build our algorithms on this method.
