MINIMUM AUGMENTATION OF ANY CONNECTED GRAPH TO A K-EDGE-CONNECTED GRAPH.

For an undirected multigraph G//0 equals (V, E//0 ) and a positive integer K, the problem of minimum augmentation of G//0 with respect to K-edge-connectivity (or K-MA) is to find a minimum set of edges E which, when added to G//0 , results in an K-edge-connected graph G equals G//0 plus E equals (V, E//0 U E). The problem of K-MA is considered in the general case where the existing graph G//0 can be any connected graph and an efficient algorith is presented. Two new concepts, extended augmentation and irreducible graph, are defined and studied. The estimation of the lower bound for the number of augmenting edges is tight and achievable by the algorithm.