Finding the edge connectivity of directed graphs

Abstract

We present two algorithms for finding the edge connectivity of a given directed graph G. The first algorithm runs in O(nm) time, where n is the number of vertices and m is the number of edges in G. The second algorithm runs in O(λ2n2) time, where λ is the edge connectivity of G. Combining both algorithms yields an O(MIN{m, λ2n}n) time algorithm for finding the edge connectivity of directed graphs. We also present an O(MIN{m, k2n}n) time algorithm for deciding whether the edge connectivity of a given directed graph G is at least k. Both algorithms are superior to the best known algorithms for finding the edge connectivity of directed graphs. © 1989.