  We study the minimum connected sensor cover problem (MIN-CSC) and the
budgeted connected sensor cover (Budgeted-CSC) problem, both motivated by
important applications (e.g., reduce the communication cost among sensors) in
wireless sensor networks. In both problems, we are given a set of sensors and a
set of target points in the Euclidean plane. In MIN-CSC, our goal is to find a
set of sensors of minimum cardinality, such that all target points are covered,
and all sensors can communicate with each other (i.e., the communication graph
is connected). We obtain a constant factor approximation algorithm, assuming
that the ratio between the sensor radius and communication radius is bounded.
In Budgeted-CSC problem, our goal is to choose a set of $B$ sensors, such that
the number of targets covered by the chosen sensors is maximized and the
communication graph is connected. We also obtain a constant approximation under
the same assumption.
