BESTCUT has a different way of computing the cut weight than Min-Cut and a different way of stopping the cut 2 . Moreover, we have slightly modified the Min-Cut procedures. BESTCUT replaces the bottom-up search in a tree representation (as it was performed in<cite> (Luo et al., 2004)</cite> ) with the top-down problem of obtaining the best partitioning of a graph.