基于并行约束规划的最大团识别研究

• 作者: 张重鹏 王宁 王珊珊 聂紫阳 肖成龙
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 最大团问题 约束规划 负载均衡 并行计算 BMT图划分策略
• 年，卷（期）: 2020,（4）
• 所属期刊栏目: 人工智能与模式识别
• 页码范围: 53-59,69
• 页数: 8页
• 分类号: TP301
• 字数: 6241字
• 语种: 中文
• DOI: 10.19678/j.issn.1000-3428.0054077

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	肖成龙	辽宁工程技术大学软件学院	28	75	4.0	8.0
2	张重鹏	辽宁工程技术大学软件学院	2	0	0.0	0.0
3	王珊珊	辽宁工程技术大学软件学院	6	3	1.0	1.0
4	王宁	辽宁工程技术大学软件学院	6	10	2.0	3.0
5	聂紫阳	辽宁工程技术大学软件学院	2	0	0.0	0.0