|
|
|
| An Improved Distributed Algorithm for Maximum Weight Independent Set (MWIS) Problem |
| Wang Xiang-yang Zhang Yuan |
| National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China |
|
|
|
|
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.
|
|
Received: 18 July 2011
|
|
|
|
Corresponding Authors:
Zhang Yuan
E-mail: y.zhang@seu.edu.cn
|
|
|
|
|
|
|
2012, Vol. 34 
