My question consists of two parts.

  1. 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?

  1. 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]?
  • $\begingroup$ 1. Please ask only one question per post. 2. "best possible way" - This is subjective, as it's not clear what you mean by "best". What's best may be a matter of opinion. Can you specify how you will evaluate answers? What are your requirements? What approaches have you considered, and why did you reject them? $\endgroup$ – D.W. Feb 16 '16 at 0:34

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?".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.