Key points are not available for this paper at this time.
Given an undirected graph G = (V, E), it is known that its edge-connectivity (G) can be computed by solving O (| V |) max-flow problems. The best time bounds known for the problem are O ( (G) | V |²), 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 | + \ (G) | V |², p | V | + | V |² | V | \) time algorithm for computing the edge-connectivity (G) of a multigraph G = (V, E), where p (| 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 |² | V |) time.
Nagamochi et al. (Sat,) studied this question.