
Boost : 
Subject: Re: [boost] [BGL] Stoer–Wagner mincut algorithm
From: Dan Jiang (danjiang_at_[hidden])
Date: 20100705 14:47:00
Hi Daniel,
Thanks for the clarification.
What I really need to is to find source set of a mincut between s(source) and t(target) in a directed graph, and hence a maximum closure of the graph. So, I need to find a st mincut, not just any mincut. Can StoerWager's mincut be forced to find st mincut only (and thus has reduced time complexity)? If not then, I guess I'll have to stick with a maxflow algorithm.
Thanks,
Dan
> Date: Mon, 5 Jul 2010 13:51:41 0400
> From: dtrebbien_at_[hidden]
> To: boost_at_[hidden]
> Subject: Re: [boost] [BGL] Stoer–Wagner mincut algorithm
>
> > Hi Daniel,
> > I wonder if your mincut algorithm can be used to find max flow, since
> > mincut and maxflow are dual? I am currently using two maxflow
> > implementations in BOOST (i.e, Goldberg and Kolmogorov). What is the
> > complexity compared to the two maxflow implementations in BOOST. I am
> > looking for fastest max flow implementation available.
> > Another related question: does BOOST offer parallel implementation of any
> > maxflow algorithm?
> > Thanks
> > Dan
>
> Hi Dan,
>
> I should have been more precise. Given two vertices s and t where s is
> called the source and t is called the sink, the maximum flow from s to
> t is equal to the weight of a minimum st cut. Thus, a maximum flow
> algorithm can compute a minimum st cut of a graph. The Stoer–Wagner
> algorithm which I implemented calculates a mincut of the graph, which
> is a slightly different problem.
>
> A cut of an undirected graph G = (V, E) is a partition of the vertices
> into two, nonempty sets X and Y = V  X. The weight w(X, Y) of a cut
> is the number of edges between X and Y if G is unweighted, or the sum
> of the weights of edges between X and Y if G is weighted. Given two
> vertices s and t, an st cut is a cut (X, Y) that separates s and t;
> that is, either s is in X and t is in Y or t is in X and s is in Y. A
> minimum st cut is an st cut of minimal weight.
>
> Historically, one way of computing a mincut of a graph was to
> calculate the maxflow for every pair of vertices (s, t) and simply
> pick a minimum st cut of minimal weight. This would be a mincut.
>
> I think that it is correct to say that if a mincut is (X, Y), then
> for all x in X and y in Y, (X, Y) is also a minimum xy cut with the
> maxflow from x to y and vice versa (because G is undirected) being
> the mincut weight w(X, Y). I think that it is also correct to say
> that the least maximum flow between any two vertices of a graph is the
> weight of a mincut.
>
> Intuitively speaking, because maximum flow is calculated between a
> given source and sink, then a maximum flow algorithm will be better
> than an mincut algorithm, which has to consider all pairs of
> vertices. So, if you are given two vertices s and t and you want to
> know the maximum flow from s to t, you should use a maximum flow
> algorithm. Also, a mincut (X, Y) of G as returned by the Stoer–Wagner
> algorithm might not be a minimum st cut; both s and t could be in X
> or Y.
>
> As far as parallel implementations of maximum flow algorithms, I do
> not know whether Parallel BGL offers parallel maximum flow algorithm
> implementations.
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_________________________________________________________________
Turn downtime into playtime with Messenger games
http://go.microsoft.com/?linkid=9734385
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk