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].











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)