一种改进的分布式最大权独立集算法
doi: 10.3724/SP.J.1146.2011.00732
An Improved Distributed Algorithm for Maximum Weight Independent Set (MWIS) Problem
-
摘要: 能快速准确寻找给定图中的最大权独立集的分布式算法，对于解决无线网络中的资源调配、无线骨干网构建等问题具有非常重要的指导意义。该文以基于最大乘信用传播的分布式算法为框架，假设所有节点了解自己邻居节点之间的局部拓扑信息，启发式地提出一种新的相邻节点间交换消息的计算方法以及相应的分布式最大权独立集算法。仿真结果表明，所提算法摆脱了文献中已有算法对图结构必须是树或者二分图的要求，且权和性能优于已有的分布式算法。Abstract: Distributed algorithms which can find the Maximum Weight Independent Set (MWIS) of graphs are very important for the design of wireless networks. Based on the max-product belief propagation framework, a new distributed MWIS algorithm is proposed. In this algorithm, each node is assumed knowing the local connection information among its neighbors. Helped by this local information, the proposed algorithm outperforms existing algorithms which requirs that the graph must be tree or bipartite, which is verified by simulation results.
-
计量
- 文章访问数: 3918
- HTML全文浏览量: 80
- PDF下载量: 1036
- 被引次数: 0
下载:
