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

A Heuristic Distributed Algorithm for the Maximum Weight Independent Set Problem

作　　者：杜鹏[1] 

机构地区：[1]南京邮电大学自动化学院,江苏南京210023

出　　处：《南京邮电大学学报（自然科学版）》2013年第6期18-23,28,共7页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

基　　金：南京邮电大学校科研基金(XK0050908049)资助项目

摘　　要：从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树(Tree)算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树(m-Tree)算法。理论分析表明,当图为树或二分图时,m-Tree算法可以简化为基于信用传播(BP)的分布式算法,是对BP算法的一种推广。仿真结果表明,对于树或二分图情形,m-Tree算法与BP算法都能收敛至最优解;对于一般图情形,m-Tree算法的收敛性能与权和性能均远优于BP算法,并且其权和性能接近最优解。Starts from the 0-1 integer programming formulation,a basic tree algorithm is proposed.This algorithm is proved to be the optimal if the graph is a tree.Then,this paper considers the general graph case and proposes the m-Tree algorithm which is a heuristic modification of the basic Tree algorithm.Analysis and simulation results show that the m-Tree algorithm is the same as the belief propagation （BP） based algorithm for tree or bipartite graph cases,and much better than the BP algorithm for the general graph case.

关 键 词：分布式算法 最大独立集 0-1整数规划 信念传播 

分 类 号：TN915.01[电子电信—通信与信息系统] TN911[电子电信—信息与通信工程]