Augmenting Graphs to Meet Edge-Connectivity Requirements (Q3989009)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 33675
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Augmenting Graphs to Meet Edge-Connectivity Requirements |
scientific article; zbMATH DE number 33675 |
Statements
Augmenting Graphs to Meet Edge-Connectivity Requirements (English)
0 references
28 June 1992
0 references
combinatorial optimization
0 references
edge-connectivity
0 references
polynomial time algorithm
0 references
splitting theorems
0 references
polymatroids
0 references
0.8725244402885437
0 references
0.8467260599136353
0 references
0.8448176383972168
0 references
0.8443552255630493
0 references
0.8366371989250183
0 references
What is the minimum number of edges to be added to a given graph \(G\) so that in the resulting graph the edge-connectivity between every pair \(\{u,v\}\) of its nodes is at least a prescribed value \(r(u,v)\)? In this splendid paper, the author finds a min-max formula for this number and describes a polynomial time algorithm to compute it. The directed counterpart is shown to be NP-complete in general but is solved in the case \(r(u,v)\equiv k\geq 1\). The proof uses splitting theorems of \textit{W. Mader} [Ann. Discrete Math. 3, 145-164 (1978; Zbl 0389.05042)] and Lovász, which are given new proofs. It also uses techniques concerning submodular functions and polymatroids. However, the author has generously converted the proofs so as to avoid this theory, and supplies details of the relationship in separate sections.
0 references