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

摘要：

最小支配集问题(MDS)是图论中的一个重要问题,在网络资源配置中有广泛的应用.上述问题是一个NP难问题,传统的启发式算法求解最小支配集问题时速度慢,且易于陷入局部最优解.将上述问题原有的无向图转化为对应的因子图,基于因子图构建最小支配集问题的线性规划方程,将方程代入图模型(GM)中,设计了一种求解最小支配集问题的置信传播算法.当算法收敛时,获得每个节点取值的边缘概率,利用边缘概率高概率地决定最小支配集节点.在随机生成的无向图上进行数值实验,结果表明,算法有效.

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

所属期刊栏目：39

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金;北方民族大学重大专项;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目

在线出版日期：2023-02-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：387-391,397