Research Article
On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks
@INPROCEEDINGS{10.4108/ICST.WICON2008.4862, author={Peng Wang and Stephan Bohacek}, title={On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks}, proceedings={4th International ICST Conference on Wireless Internet}, publisher={ICST}, proceedings_a={WICON}, year={2010}, month={5}, keywords={Maximum Weighted Independent Set; Optimal Scheduling; Wireless Mesh Network}, doi={10.4108/ICST.WICON2008.4862} }- Peng Wang
Stephan Bohacek
Year: 2010
On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks
WICON
ICST
DOI: 10.4108/ICST.WICON2008.4862
Abstract
It is well known that the maximum weighted independent set (MWIS) problem is NP-complete. Moreover, optimal scheduling in wireless networks requires solving a MWIS problem. Consequently, it is widely believed that optimal scheduling cannot be solved in practical networks. However, there are many cases where there is a significant difference between worst-case complexity and practical complexity. This paper examines the practical complexity of the MWIS problem through extensive computational experimentation. In all, over 10000 topologies are examined. It is found that the MWIS problem can be solved quickly, for example, for a 2048 node topology, it can be solved in approximately one second. Moreover, it appears that the average computational complexity grows polynomially with the number of nodes and linearly with the mean degree of the conflict graph.