Augmenting undirected edge connectivity in Õ(n2) time

Augmenting undirected edge connectivity in Õ(n2) time
复制标题

在 Õ(n2) 时间内增强无向边缘连通性

DOI：
10.1006/jagm.2000.1093
复制
发表时间：
2000
期刊：
J. Algorithms
影响因子：
--
通讯作者：
David R Karger
David R Karger
中科院分区：
--
文献类型：
--
作者：
A. Benczúr;David R Karger

文献摘要

被引文献

相似文献

我们提供了改进的随机算法（蒙特卡洛）算法，用于不向边缘分裂和边缘连接性增强问题。在M边图上的确定性。
We give improved randomized (Monte Carlo) algorithms for undirected edge splitting and edge connectivity augmentation problems. Our algorithms run in time O(n 2 ) on n-vertex graphs, making them an Ω(m/n) factor faster than the best known deterministic ones on m-edge graphs.