Approximation algorithms for facility location prob lems in 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 coding theory etc In this thesis minimum dominating set problem and some of its variants such as maximum distance d independent set minimum distance d dominating set minimum d distance m tuple r dominating set minimum vertex edg...