Sangha, Pavan and Zito, Michele
(2020)
Independent sets in Line of Sight networks.
Discrete Applied Mathematics, 286.
pp. 100-115.
|
Text
typeinst.pdf - Author Accepted Manuscript Download (671kB) | Preview |
Abstract
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: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3040628 |
Dimensions
Dimensions
