Independent Sets in Line of Sight Networks



Sangha, PS
(2018) Independent Sets in Line of Sight Networks. PhD thesis, University of Liverpool.

[img] Text
200981506_Sep2018.pdf - Unspecified

Download (2MB)

Abstract

In this thesis we study the maximum independent set problem in both 2 and higher dimensional line of sight networks. The maximum independent set problem seeks to find a largest set of pairwise disjoint vertices and we will study both the decision version and the optimisation version of the problem in this thesis. The line of sight network model was introduced to provide a model of geometric graph that incorporates both range and line of sight restrictions. A LoS network model is governed by three parameters: n-size of the underlying integer grid, d-dimension of the underlying integer grid and ω the range parameter that governs how large the communication range of each vertex is, which can range from 1 to n. We first analyse the computational complexity of the maximum independent set problem for varying classes of line of sight networks governed by the dimension and range parameters d and ω. In particular, we are interested in the cases where d ≥ 2 and ω is sublinear in the size of the integer grid and where d ≥ 3 and ω is equal to the size of the integer grid, thus maximising the communication range. This naturally leads us to the design of a number of approximation algorithms for various classes of line of sight networks where the maximum independent set problem is NP-hard. Finally we study the maximum independent set problem in a restricted 2-dimensional line of sight network model. In this model, we show that the maximum independent set problem has a connection to a scheduling application. We show how methods that we develop for solving the maximum independent set problem, can also be used to solve the scheduling problem in both an offline and semi-online setting.

Item Type: Thesis (PhD)
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 20 Aug 2019 14:19
Last Modified: 03 Aug 2021 00:12
DOI: 10.17638/03026864
Supervisors:
  • Zito, Michele
URI: https://livrepository.liverpool.ac.uk/id/eprint/3026864