k-vertex-connectivity minimum augmentation for undirected unweighted graphs.
From MaRDI portal
(Redirected from Publication:1407835)
\(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs.
\(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs.
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)\).
Recommendations
Cited in
(16)- A smallest augmentation to 3-connect a graph
- An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
- On the optimal vertex-connectivity augmentation
- The \((2, k)\)-connectivity augmentation problem: algorithmic aspects
- scientific article; zbMATH DE number 1617267 (Why is no real title available?)
- scientific article; zbMATH DE number 1670666 (Why is no real title available?)
- Connectivity augmentation of graphs
- An algorithm for construction of ak-connected graph with minimum number of edges and quasiminimal diameter
- Minimum augmentation of a tree to a K-edge-connected graph
- The minimum augmentation of any graph to aK-edge-connected graph
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time
- scientific article; zbMATH DE number 2080985 (Why is no real title available?)
- scientific article; zbMATH DE number 1555937 (Why is no real title available?)
- Hardness of \(k\)-vertex-connected subgraph augmentation problem
- Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)
This page was built for publication: \(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1407835)
