CODEWITHSUNDEEP
algorithmgraph
palatok
palatok

Reputation: 1034

minimum cost to make an undirected graph disconnected

What is the minimum cost to make an undirected weighted(positive weight) graph disconnected.

i mean i have to find out those edges which removal disconnect the graph and their cost is minimized.

I have following ideas...

1.find out all the bridges of the graph . then the bridge edge of minimum weight wiil be the ans.

2.if there is no bridge that means all the nodes are in a cycle(i'm not sure about it). then i sort the edge according to their weight and the sum of the two minimum edge weight will be the ans.

The graph has no self loop.

Is this algo correct?

Upvotes: 0

Views: 1327

Answers (1)

adelbertc
adelbertc

Reputation: 7320

This question looks to be the same question answered by the study of "minimum cuts" in graphs. I would recommend the following reading here and here to learn more about why it works from a graph theoretic point of view - the link provides some pseudocode as well.

Regarding your proposed algorithm, finding the bridges in a graph may get tricky.. you would have to inspect both endpoints and their local structure to confirm the existence of a bridge.. using edge contraction perhaps would be simpler to implement.

Upvotes: 0

Related Questions