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 $\varepsilon$ for a complete signed graph with $n$ vertices and $m$ positive edges where $\alpha(G)$ is the arboricity of the graph. Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting where edge sign flipping and vertex addition/removal are allowed. Constructing this index costs $O(m)$ memory and $O(m\times\alpha(G))$ time. We also studied the structural properties of the non-agreement measure used in the approximation algorithm. The theoretical results are accompanied by a full set of experiments concerning seven real-world graphs. These results shows superiority of our index-based algorithm to the non-index one by a decrease of %34 in time on average.
翻译:在本文中, 我们降低相关组合问题的复杂度, 从 $O (m\time\left ( 2+\alpha (G)\right)+n) 美元到 $(m+n) 美元( m+n) 美元( 任何给定值) 美元( varepsilon) 美元), 用于一个完整的签名图形, 上面写有 $n vertices 和 $m$( G) 的正边, 上面写有 $\ alpha (G) 是图的偏差。 我们的方法给出了与原始算法相同的输出, 并使得能够在一个完全动态环境中执行算法, 允许边缘标志翻转和顶端添加/ 移除。 构建这个指数成本 $( m) 美元( m) 内存和 $O( m\time\ alpha) 美元( G) 时间 。 我们还研究了近似算法中使用的非协议计量的结构性属性属性特性。 。 在理论结果中, 伴以七张真实世界图作全套实验。 这些实验的结果显示, 我们基于指数算法的算法比非索引算法的算法优于非索引算法比非索引值之一, 平均减少% 34 。 这些时间减少 34% 。