Towards the Complexity of the Widest Path Problem in Hybrid Multi-Channel WMNs
Martin Backhaus, Guenter Schaefer · 2020
Finding a widest path to transmit the maximum possible data rate is well-known in the field of computer science. For computational complexity, the network type has a significant impact: It is relatively easy to solve for simple graphs, whereas it is NP-complete for wireless networks based on slotted time models. These models neither facilitate the problem of finding widest paths, nor are they best suited to reflect realistic networks based on IEEE802.11. Therefore, this paper studies the widest path problem for hybrid multi-channel Wireless Mesh Networks (WMNs) without slotted time. In our model, wireless data rates are equally shared among edges within interference range. We prove NP-completeness of the widest path problem (even for a simpler model), but heuristics already demonstrated good results in practical settings.