Augmenting Graphs to Meet Edge-Connectivity Requirements

From MaRDI portal





What is the minimum number of edges to be added to a given graph \(G\) so that in the resulting graph the edge-connectivity between every pair \(\{u,v\}\) of its nodes is at least a prescribed value \(r(u,v)\)? In this splendid paper, the author finds a min-max formula for this number and describes a polynomial time algorithm to compute it. The directed counterpart is shown to be NP-complete in general but is solved in the case \(r(u,v)\equiv k\geq 1\). The proof uses splitting theorems of \textit{W. Mader} [Ann. Discrete Math. 3, 145-164 (1978; Zbl 0389.05042)] and Lovász, which are given new proofs. It also uses techniques concerning submodular functions and polymatroids. However, the author has generously converted the proofs so as to avoid this theory, and supplies details of the relationship in separate sections.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Augmenting Graphs to Meet Edge-Connectivity Requirements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3989009)