PACKING ALGORITHMS FOR ARBORESCENCES (AND SPANNING-TREES) IN CAPACITATED GRAPHS

In a digraph with real-valued edge capacities, we pack the greatest nu mber of arborescences in time O(n(3)m log(n(2)/m)); the packing uses a t most in distinct arborescences. Here n and m denote the number of ve rtices and edges in the given graph, respectively. Similar results hol d for integral packing: we pack the greatest number of arborescences i n time O(min{n, log N} n(2)m log (n(2)/m)) using at most m + n - 2 dis tinct arborescences; here N denotes the largest (integral) capacity of an edge. These results improve the best previous bounds for capacitat ed digraphs. The algorithm extends to several related problems, Includ ing packing spanning trees in an undirected capacitated graph, and cov ering such graphs by forests. The algorithm provides a new proof of Ed monds' theorem for arborescence packing, for both integral and real ca pacities, based on a laminar family of sets derived from the packing. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsev ier Science B.V.