Boost Users :
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
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:
contains an implementation of finding the Gomory-Hu tree (a building block
of Vazirani's algorithm).
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net