Augmenting edge and vertex connectivities simultaneously
From MaRDI portal
What is the minimum number of edges one has to add to a graph \(G\) so that the edge-connectivity and the vertex-connectivity of each pair of vertices \(x,y\) of \(G\) is at least the number \(a(x,y)\) and \(b(x,y)\), respectively, where the numbers \(a(x,y), b(x,y)\) are assigned in beforehand? The authors show the the above stated problem can be solved in a polynomial time if \(b(x,y)=2\) for all \(x,y\) in \(G\). For the entire collection see [Zbl 0879.00060].
Recommendations
Cited in
(6)- Hypergraph connectivity augmentation
- Directed vertex-connectivity augmentation
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- scientific article; zbMATH DE number 1372654 (Why is no real title available?)
- Augmenting edge-connectivity between vertex subsets
- Graph connectivity and its augmentation: Applications of MA orderings
This page was built for publication: Augmenting edge and vertex connectivities simultaneously
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4370202)