CATS-Mar-7-2014
Title[edit]
Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems
Speaker[edit]
Kanthi Kiran Sarpatwar, University of Maryland
Abstract[edit]
In the well studied "Connected Dominating Set" (CDS) problem, we are given an unweighted graph and the goal is to find a minimum size dominating set, with an additional restriction that it induces a connected subgraph in the given graph. Guha and Khuller (Algorithmica, 1998) obtained the first O(log n) approximation algorithm for this problem. In this talk, we will discuss new approximation algorithms for a partial and budgeted version of the CDS problem. In the partial connected dominating set problem (PCDS), the goal is to find a min size subset that induces a connected subgraph, while dominating at least a given fraction of vertices. The budgeted CDS problem (BCDS) is a dual problem, where the size of the subset is fixed and we seek to maximize the number of vertices that can be dominated. We will discuss, an O(log n) and a constant approximation algorithm for the PCDS and BCDS problems respectively. Further, we will extend our results to a more generalized framework that has the capacitated version of these problems as a special case.
