CODEWITHSUNDEEP
graphnetwork-flow
eddyrokr
eddyrokr

Reputation: 414

Algorithm to find all the cuts in a graph

I am looking for an efficient algorithm which can help me to list out all the cuts in a graph. The graph is a flow network (directed graph) and has a source and a sink fixed. I want to find out what are all the possible cut sets with source on one side and sink on the other.

Please note that the priority is to find all the cut sets and not the minimum cut.

For example, consider a graph with the following edge lists: s-->a-->t s-->b-->t

The cut sets of the above graph is : {sa,sb}, {at,bt}, {sa,sb,at}, {sa,sb,bt}, {sa,sb,at,bt}

Upvotes: 1

Views: 2249

Answers (1)

member555
member555

Reputation: 807

It's cant be efficent because you have exponencial amount of cuts. You have the source is S,the sink in T, where S-T is the cut. Now think about this: for every vertex,it can be in S,or in T. Think about all the vertices as a long binary number,where 1 means vertex i is in S,and 0 means its in T.

How many options do you have? if you have n vertices,how many different binary numbers you can have? the answer is 2^n, but we can ignore the sink and the soruce,but it doesnt mother, we still have O(2^n) for diffrent cuts.

Upvotes: 1

Related Questions