In the fully dynamic edge connectivity problem, the input is a simple graph $G$ undergoing edge insertions and deletions, and the goal is to maintain its edge connectivity, denoted $\lambda_G$. We present two simple randomized algorithms solving this problem. The first algorithm maintains the edge connectivity in worst-case update time $\tilde{O}(n)$ per edge update, matching the known bound but with simpler analysis. Our second algorithm achieves worst-case update time $\tilde{O}(n/\lambda_G)$ and worst-case query time $\tilde{O}(n^2/\lambda_G^2)$, which is the first algorithm with worst-case update and query time $o(n)$ for large edge connectivity, namely, $\lambda_G = \omega(\sqrt{n})$.
翻译：在完全动态边连通性问题中，输入是一个经历边插入和删除的简单图 $G$，目标是维护其边连通性，记为 $\lambda_G$。我们提出了两种解决此问题的简单随机化算法。第一种算法以每次边更新的最坏情况更新时间为 $\tilde{O}(n)$ 来维护边连通性，这与已知界限匹配，但分析更为简单。我们的第二种算法实现了最坏情况更新时间为 $\tilde{O}(n/\lambda_G)$ 和最坏情况查询时间为 $\tilde{O}(n^2/\lambda_G^2)$，这是首个对于较大边连通性（即 $\lambda_G = \omega(\sqrt{n})$）具有最坏情况更新和查询时间为 $o(n)$ 的算法。
相关内容
微信扫码咨询专知VIP会员