Minimal edge-coverings of pairs of sets (Q1898731)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal edge-coverings of pairs of sets |
scientific article |
Statements
Minimal edge-coverings of pairs of sets (English)
0 references
20 September 1995
0 references
The authors' main result is a max-min theorem concerning bisupermodular functions on pairs of sets. Their result has a number of non-trivial consequences. It gives rise to a max-min formula for the minimum number of edges to be added to a digraph \(D\) to make it \(k\)-node-connected and it implies a generalization of an edge-connectivity augmentation theorem of the first author; it also implies Mader's theorem on splitting of edges in digraphs, Edmond's theorem on matroid partitions, as well as an extension of Lubiw's extension of Györi's theorem on intervals.
0 references
edge-coverings
0 references
max-min theorem
0 references
digraph
0 references
edge-connectivity augmentation theorem
0 references