\(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs. (Q1407835)
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 1983615
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | \(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs. |
scientific article; zbMATH DE number 1983615 |
Statements
\(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs. (English)
0 references
24 March 2004
0 references
The authors provide an algorithm for the following problem: Given a graph \(G=(V(G),E(G))\) and a number \(k\). Find a minimum set \(E'\) of edges not in \(E(G)\) so that adding edges in \(E'\) to \(G\) results in a \(k\)-connected graph. The complexity of the algorithm is \(O(k| V(G)| ^5)\).
0 references
connectivity
0 references
algorithm
0 references
0.8929426074028015
0 references
0.8754194974899292
0 references
0.8701468110084534
0 references
