We present an algorithm which calculates a minimum cut and its weight in an undirected graph with nonnegative real edge weights, n vertices and m edges, in time O((max (log n, min (m/n,δ_G/ε))n~2), where ε is the minimal edge weight, and δ_G the minimal weighted degree. For integer edge weights this time is further improved to O(δ_Gn~2) and O(λ_Gn~2). In both cases these bounds are improvements of the previously known best bounds of deterministic algorithms. These were O(nm + log nn~2) for real edge weights and O(nM + n~2) and O(M + λ_Gn~2) for integer weights, where M is the sum of all edge weights.
展开▼
