In a digraph with real-valued edge capacities, we pack the greatest number of arborescences in time O(n3m log(n2/m)); the packing uses at most m distinct arborescences. Here n and m denote the number of vertices and edges in the given graph, respectively. Similar results hold for integral packing: we pack the greatest number of arborescences in time O(min{n, log N}n2m log(n2/m)) using at most m + n − 2 distinct arborescences; here N denotes the largest (integral) capacity of an edge. These results improve the best previous bounds for capacitated digraphs. The algorithm extends to several related problems, including packing spanning trees in an undirected capacitated graph, and covering such graphs by forests. The algorithm provides a new proof of Edmonds' theorem for arborescence packing, for both integral and real capacities, based on a laminar family of sets derived from the packing.
