World's most popular travel blog for travel bloggers.

[Answers] Edge-connectivity of a weighted undirected graph

, , No Comments
Problem Detail: 

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]?
Asked By : Rajat

Answered By : Juho

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback