2

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.

snakile
  • 52,936
  • 62
  • 169
  • 241
m b
  • 61
  • 6

1 Answers1

3

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.

Matthieu Latapy
  • 173
  • 9
snakile
  • 52,936
  • 62
  • 169
  • 241
  • thanks a lot!. Can I just remove a random edge(witch is sort by weight in ascending order ) and then try to find spanning tree(O(|V|+|E|)) for graph, if spanning tree not available then I can say the removed edge make graph disconnected and we have two disjoint sets.Then I check the size of disjoint sets.I suppose finding size of sets is in order of O(V). Am I correct? I am not really need sets with equal sizes but it better to be in near proportions. – m b Oct 10 '16 at 14:58
  • If I find an edge that make two disjoint sets with 10 and 90 percent proportion, that would be satisfiable. I want do this procedure in recursive manner for dividing graph into two disjoint sets that has lost fewer edges as long as possible. – m b Oct 10 '16 at 14:58