计算机工程

作者：肖成龙, 聂紫阳, 王宁, 张重鹏, 王珊珊

单位：辽宁工程技术大学 软件学院, 辽宁 葫芦岛 125105

关键词：最大团问题,约束规划,负载均衡,并行计算,BMT图划分策略

基金：国家自然科学基金（61404069）；辽宁省教育厅科学研究项目（LJYL048）；辽宁省教育厅青年项目（LJ2017QL033）。

为提高大数据平台下大规模图例的最大团问题求解效率，提出一种基于并行约束规划的最大团识别算法。通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图，并将其分配给Spark集群中的计算节点，每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解，实现最大团问题的并行化处理。引入时间预测模型，设计基于任务运行时间预测模型的并行图划分方法，从而有效解决计算节点的负载均衡问题。实验结果表明，与基于BMC图划分策略的最大团并行识别算法相比，该算法具有更高的求解效率，可取得近似线性的加速比。

来源：2020年第4期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第4期