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

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 grap