一种启发式的分布式最大独立集算法

• 作者: 杜鹏
• 来源期刊: 南京邮电大学学报（自然科学版）
• 学科: 工学
• 关键词: 分布式算法 最大独立集 0-1整数规划 信念传播
• 年，卷（期）: 2013,（6）
• 所属期刊栏目: 通信与电子
• 页码范围: 18-23,28
• 页数: 7页
• 分类号: TN915.01|TN911
• 字数: 6468字
• 语种: 中文

摘要

从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树(Tree)算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树(m-Tree)算法.理论分析表明,当图为树或二分图时,m-Tree算法可以简化为基于信用传播(BP)的分布式算法,是对BP算法的一种推广.仿真结果表明,对于树或二分图情形,m-Tree算法与BP算法都能收敛至最优解;对于一般图情形,m-Tree算法的收敛性能与权和性能均远优于BP算法,并且其权和性能接近最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杜鹏	南京邮电大学自动化学院	8	8	2.0	2.0