An Improved Distributed Algorithm for Maximum Weight Independent Set (MWIS) Problem

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.