An application of submodular flows (Q1119596)

The authors generalize some theorems of Rado and Lovász concerning bipartite graphs and intersecting supermodular functions. As a general model, an optimization problem of finding a supporting set of a matroid having minimum cost is formulated. Several applications of the general results are given for the bipartite graphs and for the optimization problem of finding a minimum-cost subgraph H of a digraph G such that H contains k disjoint paths from a fixed node of G to any other nodes. A characterization for graphs having a branching that meets all directed cuts is obtained. A result of Vidyasankar concerning the optimal covering of a directed graph by arborescences and a theorem of Gröflin and Hoffman on matroid intersection are also extended. Some problems of improving networks are also discussed.