Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
Authors:
- Jørgen Bang-JensenJBJørgen Bang-Jensen
- András FrankAFAndrás Frank
- Bill JacksonBJBill Jackson
- 1 May 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 8 (2) , 155-178
Abstract
Generalizing and unifying earlier results of W. Mader, and A. Frank and 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 resulting graph satisfies local edge-connectivity prescriptions. An extension of Edmonds’s theorem on disjoint arborescences is also deduced along with a new sufficient condition for the solvability of the edge-disjoint paths problem in digraphs. The approach gives rise to strongly polynomial algorithms for the corresponding optimization problems.Keywords
This publication has 17 references indexed in Scilit:
- Applications of submodular functions1993
- On a theorem of MaderDiscrete Mathematics, 1992
- Augmenting Graphs to Meet Edge-Connectivity RequirementsSIAM Journal on Discrete Mathematics, 1992
- The minimum augmentation of any graph to a K‐edge‐connected graphNetworks, 1989
- A new approach to the maximum-flow problemJournal of the ACM, 1988
- Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphsJournal of Graph Theory, 1988
- On Connectivity Properties of Eulerian Digraphs1988
- Optimal Mixed Graph AugmentationSIAM Journal on Computing, 1987
- Augmentation ProblemsSIAM Journal on Computing, 1976
- Connectivity in digraphsJournal of Combinatorial Theory, Series B, 1973