My question consists of two parts.Let say the edge connectivity of a graph is K. I would like to change the edge connectivity value to L (> K). What is the best possible way to do so?My guess: Obviously, we have to increase the edge weight of one of the critical edges (edges of the min-cut), but among the set of critical edges which edge should we choose?After changing the weight of one of the critical edges, how could we find the new edge connectivity of the graph [assume we have already computed the edge connectivity of the previous graph]?
Edge-connectivity of a weighted undirected graph
graphs;weighted graphs
This is generally known as edge connectivity augmentation, and there is a lot of literature on the subject. There are several fast algorithms for the task, and they come in different flavors depending on what you know about your graph, or what you specifically care about.A basic question is what is the minimum number of edges (or minimum cost of edges) to be added to the graph $G$ to increase its edge connectivity to a certain value?.