In this paper we present new edge splitting-off results maintaining all-pairs edge-connectivities of a graph. We first give an alternate proof of Mader's theorem, and use it to obtain a deterministic O(r_(max)~2 · n~2)-time complete edge splitting-off algorithm for unweighted graphs, where r_(max) denotes the maximum edge-connectivity requirement. This improves upon the best known algorithm by Gabow by a factor of Ω(n). We then prove a new structural property, and use it to further speedup the algorithm to obtain a randomized O(m + r_(max)~3 · n)-time algorithm. These edge splitting-off algorithms can be used directly to speedup various graph algorithms
展开▼
