Approximation algorithms for dominating set and its variants on unit disk graphs
No Thumbnail Available
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Dominating set and its variants have been studied extensively in the literature and are of broad and current research interest to many researchers due to its wide range of applications, including, but not limited to, networks, VLSI, clustering, map labeling and coding theory. In this thesis, minimum dominating set problem and some of its variants, such as minimum connected dominating set, minimum lair s dominating set, and maximum (weighted) independent set problems are studied on unit disk graphs. All the aforementioned problems are NP-hard on unit disk graphs. The high time complexity of the existing polynomial-time constant factor approximation algorithms motivated us to study these problems and design faster approximation algorithms and approximation schemes. The approximation algorithms and approximation schemes presented in this thesis outperform the existing algorithms in the literature in terms of time complexity. We introduced the liar s dominating set problem in the geometric setting. We showed that the problem is NP-hard even for unit disk graphs and designed constant factor approximation algorithms and an approximation scheme for the problem.
Description
Supervisor: Gautam K. Das
Keywords
MATHEMATICS