The k-way graph partitioning problem can be transformed into the maximum k-cut problem using a proposed technique of graph modification. It is possible to transform the graph partitioning problem into the max-cut problem by incorporating node size information into the edge weight. After transformation, a very simple cost function can be devised which makes the proposed algorithm more efficient than the Kernighan-Lin (K-L) algorithm (1970). The computing time per iteration of the algorithm is O(k*N/sup 2/), where N is the number of nodes in the given graph. Experimental results show that the proposed algorithm outperforms the K-L algorithm both in the quality of solutions and in the elapsed time. Also, as the difference between the sizes of the nodes increases, the performance gap between the proposed algorithm and the K-L algorithm becomes larger.
展开▼
机译：使用建议的图形修改技术，可以将k向图划分问题转化为最大k割问题。通过将节点大小信息合并到边缘权重中，可以将图形划分问题转换为最大割问题。变换后，可以设计一个非常简单的成本函数，该函数使所提出的算法比Kernighan-Lin（K-L）算法（1970年）更有效。该算法每次迭代的计算时间为O（k * N / sup 2 /），其中N是给定图中的节点数。实验结果表明，该算法在求解质量和经过时间上均优于K-L算法。而且，随着节点大小之间的差异增加，所提出的算法与K-L算法之间的性能差距也会变大。
展开▼
