Approximation algorithms for dominating set and its variants on unit disk graphs

Show simple item record

dc.contributor.author Jallu, Ramesh Kumar
dc.date.accessioned 2018-06-11T10:11:23Z
dc.date.available 2018-06-11T10:11:23Z
dc.date.issued 2018
dc.identifier.other ROLL NO.126123018
dc.identifier.uri http://gyan.iitg.ernet.in/handle/123456789/981
dc.description.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. en_US
dc.description.sponsorship Supervisor: Gautam K. Das en_US
dc.language.iso en en_US
dc.relation.ispartofseries TH1727;
dc.subject MATHEMATICS en_US
dc.title Approximation algorithms for dominating set and its variants on unit disk graphs en_US
dc.type Thesis en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search


Browse

My Account