Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

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 | + min \ λ ( G ) | V |² ,p | V | + | V |² log | 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 |² log | V | ) time.