CODEWITHSUNDEEP
algorithmgraphgraph-theorydisjoint-setsminimum-cut
m b
m b

Reputation: 61

Divide a graph into same size disjoint sets with minimum cut

Is there any algorithm or code that divide graph nodes into two or more disjoint sets that satisfy following conditions: first, only edges allowed to remove. second, edges are weighted and those that would be removed must has minimum weight(minimum cut algorithm). third,desired disjoint sets have same size as long as possible.

Upvotes: 2

Views: 1776

Answers (1)

snakile
snakile

Reputation: 54531

It looks like you're trying to solve the Min-bisection problem in which given a graph G you would like to partition V[G] into two disjoint subsets A and B of equal size such that the sum of weights of the edges between A and B is minimized. Unfortunately, the Min-bisection problem is known to be NP-hard. However, Kernighan–Lin algorithm is a very simple O(n^2*logn) heuristic algorithm for the problem. While very little is known about the algorithm theoretically (we do not have a proven bound on its performance relative to an optimal solution), the algorithm is shown to be quite effective in experiments: Optimization by Simulated Annealing: an Experimental Evaluation; part 1, Graph Partitioning.

Upvotes: 3

Related Questions