一种求解最小支配集问题的置信传播算法  

A Belief Algorithm Propagation for Solving Minimum Dominating Set Problem

作　　者：刘子琳 王晓峰[1,2] 芦磊 程亚南 LIU Zi-lin;WANG Xiao-feng;LU Lei;CHENG Ya-nan(Department of Computer Science,North Minzu University,Yinchuan Ningxia 750021,China;Key Laboratory of the State Ethnic Affairs Commission for Intelligent Processing of Image and Graphics,North Minzu University,Yinchuan Ningxia 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,宁夏银川750021

出　　处：《计算机仿真》2022年第12期387-391,397,共6页Computer Simulation

基　　金：国家自然科学基金资助项目(62062001,61762019,61862051,61962002);北方民族大学重大专项资助(ZDZX201901);宁夏自然科学基金项目(2020AAC03214,2020AAC03219,2019AAC 03120,2019AAC03119)。

摘　　要：最小支配集问题(MDS)是图论中的一个重要问题,在网络资源配置中有广泛的应用。上述问题是一个NP难问题,传统的启发式算法求解最小支配集问题时速度慢,且易于陷入局部最优解。将上述问题原有的无向图转化为对应的因子图,基于因子图构建最小支配集问题的线性规划方程,将方程代入图模型(GM)中,设计了一种求解最小支配集问题的置信传播算法。当算法收敛时,获得每个节点取值的边缘概率,利用边缘概率高概率地决定最小支配集节点。在随机生成的无向图上进行数值实验,结果表明,算法有效。The minimum dominating set problem is an important problem in graph theory, and it has a wide range of applications in network resource allocation. The problem is also an NP-hard problem, the traditional heuristic algorithm is slow to solve the minimum dominating set problem, and it is easy to fall into a local optimal solution. The original undirected graph of the problem is transformed into the corresponding factor graph, the linear programming equation of the minimum dominating set problem is constructed based on the factor graph, and the equation is substituted into the graph model(GM),a belief algorithm propagation for solving the minimum dominating set problem is proposed. When the algorithm converges, the edge probability of each node’s value is obtained, and the minimum dominance set node is determined by using the edge probability with high probability. Numerical experiments on randomly generated undirected graphs show that the algorithm is effective.

关 键 词：最小支配集 集合覆盖 置信传播算法 因子图 线性规划 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]