PRESERVING AND INCREASING LOCAL EDGE-CONNECTIVITY IN MIXED GRAPHS

Generalizing and unifying earlier results of W. Mader, and A. Frank an d B. Jackson, we prove two splitting theorems concerning mixed graphs. By invoking these theorems we obtain min-max formulae for the minimum number of new edges to be added to a mixed graph so that the resultin g graph satisfies local edge-connectivity prescriptions. An extension of Edmonds's theorem on disjoint arborescences is also deduced along w ith a new sufficient condition for the solvability of the edge-disjoin t paths problem in digraphs. The approach gives rise to strongly polyn omial algorithms for the corresponding optimization problems.