Min Cut Contraction: Solving Edge Connectivity Problem using Graph Contraction

This paper presents a new approach to finding edges connectivity in undirected graphs. The fundamental principle is simple: the edges in a graph's edge connectivity form an extremely small fraction of the graph's edges. Using this idea, we give a deterministic, strongly polynomial algorithm that finds the edge connectivity in an arbitrarily weighted undirected graph with high probability. The algorithm runs in O(n²log³n) time, but more simple to the previous a significant improvement over the previous O(mn) time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures.