Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach

Ali Shakiba

In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(m\times \left(2+\alpha (G)\right)+n)$ to $O(m+n)$ for any given value of $\varepsilo…