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).