0 Replies Latest reply on Nov 14, 2010 1:55 AM by 814010

# 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

Thanks
Amit