带权图的均衡k划分  

Balanced k-Way Partitioning for Weighted Graphs

作　　者：郑丽丽[1,2] 武继刚[1,2] 陈勇[1,2] 朱梅霞[1,2] 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387 [2]计算机系统结构国家重点实验室(中国科学院计算技术研究所),北京100190

出　　处：《计算机研究与发展》2015年第3期769-776,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61173032);中国科学院计算机系统结构国家重点实验室开放课题(CARCH201303)

摘　　要：带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集,使得任意2个子集中顶点的权值之和的差异达到极小,并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域,它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下,采用最大化同一子集内部边权之和的策略来构造每一个顶点子集;构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中,直到子集S的顶点权值之和满足要求.此外,采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明,当k分别取值为2,4,8时所提算法分别在86%,81%,68%的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达60%以上.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 agroup of neighboring vertices with the highest gain from its candidate subset for inclusion S until the sum of vertex-weights of Smeets 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%.

关 键 词：带权图 k划分 启发式算法 禁忌搜索 算法设计 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]