Edge-connectivity augmentation problems (Q1091147)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Edge-connectivity augmentation problems |
scientific article; zbMATH DE number 4009833
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Edge-connectivity augmentation problems |
scientific article; zbMATH DE number 4009833 |
Statements
Edge-connectivity augmentation problems (English)
0 references
1987
0 references
We give a characterization on the minimum number of edges to be added so as to k-edge-connect a graph. We also show that such a minimum edge set can be determined in \({\mathcal O}(kL| V|^ 4(k| V| +| E|))\) time for any graph \(G=(V,E)\) and any fixed \(k\geq 2\), where \(L=\min \{k,| V| \}\).
0 references
minimum edge set
0 references
