Independent sets in Line of Sight networks

Sangha, Pavan and Zito, Michele
(2020) Independent sets in Line of Sight networks. Discrete Applied Mathematics, 286. pp. 100-115.

[img] Text
typeinst.pdf - Author Accepted Manuscript

Download (671kB) | Preview


Line of Sight (LoS) networks provide a model of wireless communication which incor-porates visibility constraints. Vertices of such networks can be embedded onto the cube{(x1,x2,...,xd):xi∈{1,...,n},1≤i≤d}so that two vertices are adjacent if and onlyif their images lay on a line parallel to one of the cube edges and their distance is lessthan a given range parameterω. In this paper we study large independent sets in LoSnetworks.Weprovethatthecomputationalproblemoffindingamaximumindependentset can be solved optimally in polynomial time for one dimensional LoS networks.However, ford≥2, the (decision version of) the problem becomes NP-complete for anyfixedω≥3. In addition, we show that the problem is APX-hard whenω=nford≥3.On the positive side, we show that LoS networks generalize chordal graphs. This impliesthat there exists a simpled-approximation algorithm for the maximum independent setproblem in LoS networks. Finally, we describe a polynomial time approximation schemefor the maximum independent set problem in LoS networks for the case whenωis aconstantandpresentanimprovedheuristicalgorithmfortheprobleminthecaseω=n

Item Type: Article
Uncontrolled Keywords: Line of Sight networks, Independent sets, Approximation algorithms, Approximation hardness
Depositing User: Symplectic Admin
Date Deposited: 10 May 2019 14:50
Last Modified: 19 Jan 2023 00:46
DOI: 10.1016/j.dam.2019.03.029
Related URLs: