1.Previous
3.Next

directed graphs, terminals, and partitioning the vertices into more than two sets.

The weighted min-cut problem allowing both positive and negative weights can be trivially transformed into a weighted maximum cut problem by flipping the sign in all weights.

__TOC__

Without terminal nodes

The input is a graph G = (V, E). The required output is a partition V = S + T (a partition of the vertices into two disjoint subsets S and T). Any such partition has a cost, and the goal is

1.Previous
3.Next