Re: [Boost-users] Boost and K-Cuts

Subject: Re: [Boost-users] Boost and K-Cuts
From: Zeljko Vrba (zvrba_at_[hidden])
Date: 2009-01-25 12:40:17

On Sun, Jan 25, 2009 at 08:27:22AM +0000, Gianni Loiacono wrote:
> Hi all,
> sorry for my poor english.
> I want to know if the algorithm explained in this paper:http://www.cc.gatech.edu/~vazirani/k-cut.ps
> for finding the k-cuts (algorithm efficient) was been development in boost.
> In other words: There is in BGL some procedure that can cuts minimal a graph?
> 
No, there is not.  (If you only need 2-cuts, you can use one of the flow
algorithms)

Since I've stumbled upon this problem myself recently, I have to ask a
side-question: are you sure that you need k-cuts, and not k-way graph
partition?  (In my case I _thought_ I needed a k-way cut, but it turned out
that what I _really_ wanted was a k-way partition).  Regarding k-way
partitions, you might find "ordering" algorithms (look in the docs) useful.

If you want to try and develop it yourself, this project:

http://www.tsp.gatech.edu/concorde/

contains an implementation of finding the Gomory-Hu tree (a building block
of Vazirani's algorithm).