ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (3): 769-776.doi: 10.7544/issn1000-1239.2015.20131508

Previous Articles    

Balanced k-Way Partitioning for Weighted Graphs

Zheng Lili, Wu Jigang, Chen Yong, Zhu Meixia   

  1. (School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387) (State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190)
  • Online:2015-03-01

Abstract: Balanced k-way partitioning for a weighted graph is to divide the vertex set of the graph into k disjoint subsets, in order to minimize the difference of the sums of the vertex-weights between two subsets, together with minimizing the sum of the edge-weights, whose incident vertices belong to different subsets. This k-way partitioning problem is widely applied in the areas such as hardwaresoftware co-design, VLSI design, data partitioning, etc., and it has been proved to be NP-complete. An efficient heuristic algorithm is proposed to generate a good approximate k-way partition by maximizing the sum of the weights associated with the inner edges of the subsets, together with a relatively balanced partition. In detail, the proposed heuristic algorithm constructs a subset S by selecting a group of neighboring vertices with the highest gain from its candidate subset for inclusion S until the sum of vertex-weights of S meets the demand. Moreover, we customize an approach based on tabu search to refine the heuristic partition. Experimental results show that, the proposed algorithm works more efficiently for average solution than the state-of-the-art on 86%, 81% and 68% graphs among the public benchmark, for the cases k=2,4,8, respectively, with the improvement up to 60%.

Key words: weighted graph, k-way partitioning, heuristic algorithm, tabu search, algorithm design

CLC Number: