\(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 this page instead for the normal view: \(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs. |
scientific article; zbMATH DE number 1983615
| Language | Label | Description | Also known as |
|---|---|---|---|
| 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
