Given an undirected graph G = (V, E), it is known that its edge-connectivity lambda(G) can be computed by solving O(\V\) max-flow problems. The best time bounds known for the problem are O(lambda(G)\V\2), due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249-251) if G is simple, and O(\E\3/2\V\), due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507-518) if G is multiple.
An O(\E\ + min {lambda(G)\V\2, p\V\ + \V\2 log \V\}) time algorithm for computing the edge-connectivity lambda(G) of a multigraph G = (V, E), where p(less-than-or-equal-to \E\) is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of \V\ times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in O(\V\\E\ + \V\2 log\V\) time.