The minimum augmentation of any graph to a K‐edge‐connected graph
Guo Ray Cai, Yugeng Sun · Networks · 1989
Abstract For a graph G0 = (V, E0) and an integer K, how many edges are needed for augmenting G0 to a K‐edge‐connected graph? Results in the literature have answered this in several special cases such as when G0 is a tree, or when K = 2. In this paper, we settle the problem in the general case where G0 can be any multigraph and K can be any positive integer. We obtained both good characterization and good algorithm for the problem. Applications of our algorithm are suggested in designing a reliable network aiming at the most effective use of exising network.