We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS '20). Our algorithm uses poly-logarithmic calls to any max-flow algorithm, which yields a running time of $\tilde O(m + n^{3/2})$ and improves on the previous best time of $\tilde O(n^2)$ (Bencz\'ur and Karger, SODA '98) for this problem. We also obtain an identical improvement in the running time of the closely related edge splitting off problem in undirected graphs.
翻译：我们给出了一种算法,通过使用孤立断层框架(Li和Panigrahi,FOCS '20)来增加未定向图的边缘连通性。我们的算法将多对数调用到任何最大流算法中,这种算法产生一个运行时间为$\tilde O(m + n ⁇ 3/2})$(m + n ⁇ 3/2美元)的运行时间,并改进了以前在这个问题上的最佳时间$\tilde O(n ⁇ 2)$(Bencz\'ur和Karger,SODA '98)的运行时间。我们同样改进了在未定向图表中密切相关的边缘分割问题的运行时间。
相关内容
微信扫码咨询专知VIP会员