Advertisement
Published in:
2017 | OriginalPaper | Chapter
Finding Large Independent Sets in Line of Sight Networks
Authors : Pavan Sangha, Michele Zito
Published in: Algorithms and Discrete Applied Mathematics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Line of Sight (LoS) networks provide a model of wireless communication which incorporates visibility constraints. Vertices of such networks can be embedded in finite d-dimensional grids of size n, and two vertices are adjacent if they share a line of sight and are at distance less than \(\omega \). In this paper we study large independent sets in LoS networks. We prove that the computational problem of finding a largest independent set can be solved optimally in polynomial time for one dimensional LoS networks. However, for \(d\ge 2\), the (decision version of) the problem becomes NP-hard for any fixed \(\omega \ge 3\) and even if \(\omega \) is chosen to be a function of n that is \(O(n^{1-\epsilon })\) for any fixed \(\epsilon > 0\). In addition we show that the problem is also NP-hard when \(\omega = n\) for \(d \ge 3\). This result extends earlier work which showed that the problem is solvable in polynomial time for gridline graphs when \(d=2\). Finally we describe simple algorithms that achieve constant factor approximations and present a polynomial time approximation scheme for the case where \(\omega \) is constant.