Augmenting Graphs to Meet Edge-Connectivity Requirements (Q3989009)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 33675
Language Label Description Also known as
default for all languages
No label defined
    English
    Augmenting Graphs to Meet Edge-Connectivity Requirements
    scientific article; zbMATH DE number 33675

      Statements

      Augmenting Graphs to Meet Edge-Connectivity Requirements (English)
      0 references
      0 references
      28 June 1992
      0 references
      combinatorial optimization
      0 references
      edge-connectivity
      0 references
      polynomial time algorithm
      0 references
      splitting theorems
      0 references
      polymatroids
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references