The minimum augmentation of any graph to a K‐edge‐connected graph

Guo‐Ray ‐R Cai, Yu‐Geng ‐G Sun

Research output: Contribution to journalArticlepeer-review

64 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)151-172
Number of pages22
Issue number1
StatePublished - Jan 1989

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this