Question

I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article Enumeration in Graphs p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a faster or simpler algorithm I can use if I am interested only in the number of such cuts and I do not actually need to enumerate it?

The definition of a s-t cut I am using is following. We have a directed graph where two vertices are labelled S and T. Cut is a minimal set of edges of a graph such that by removing those edges there will no longer exist a path from vertex S to vertex T.

Was it helpful?

Solution

CSteory.StackExchange was the place! My question was answered there, in the negative.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top