0 Replies Latest reply: Nov 13, 2010 7:55 PM by 814010 RSS

    Graph Partitioning

      Hi All,
      I need some help regrading k-way graph partitioning. Lets consider and example, I have to divide my undirected, un-weighted graph (each edge weight unity) to 3 equal parts (partitions -in terms of nodes ) A,B,C -such that after partitioning

      A-B edges on A-B cut have a cost of 1* orignal weight of edges on cut A to B
      B-C edges on B-C cut have a cost of 1 * original weight of edges on cut B to C
      A-C edges on A-C cut have a cost of 2 * Ato C

      What we have to do is minimize the cost of min{(A-B cut edges) + (B-C cut edges) + (A-C cut edges)}

      How to solve it -of course not exactly but a good hueristic will do. I have acess to graph partitioner, that create equal size partitions and can reduce the cut weight... but in our problem ordering can make a difference as A,B,C will have a given cost and A C B another cost of edges on cut, A-C multiplied by 1 , B-C multiplied by 1 and A-C multiplied by 2