  In this paper, we study locating charging station problem as facility
location problem and its variants ($k$-Median, $k$-Facility location and
$k$-center). We study the connectivity and the capacity constraints in these
problem.
  Capacity and connectivity constraints have been studied in the literature
separately for all these problems. We give first constant factor approximations
when both the constraints are present. Extending/modifying the techniques used
for connected variants of the problem to include capacities or for capacitated
variants of problem to include connectivity is a tedious and challenging task.
In this paper, we combine the two constraints by reducing the problem to
underlying well studied problems, solving them as black box and combine the
obtained solutions. We also, combine the two constraints in the
prize-collection set up.
  In the prize-collecting set up, the problems are not even studied when one of
the constraint is present. We present constant factor approximation for them as
well.

Data Structures and Algorithms