A MATROID APPROACH TO FINDING EDGE-CONNECTIVITY AND PACKING ARBORESCENCES

We present an algorithm that finds the edge connectivity lambda of a graph having n vectices and m edges. The running time is O(lambda m log(n(2)/m)) for directed graphs and slightly less for undirected graphs, O(m+lambda(2)n log(n/lambda)). This improves the previous best time bounds, O(min{mn, lambda(2)n(2)}) for directed graphs and O(lambda n(2)) for undirected graphs. We present an algorithm that finds k edge-disjoint arborescences on a directed graph in time O((kn)(2)). This improves the previous best time bound, O(kmn + k(3)n(2)). Unlike previous work, our approach is based on two theorems of Edmonds that link these two problems and show how they can be solved. (C) 1995 Academic Press. Inc.