Publications

Solving the connected dominating set problem and power dominating set problem by integer programming

Fan, Neng F.; Watson, Jean-Paul W.

In this paper, we propose several integer programming approaches with a polynomial number of constraints to formulate and solve the minimum connected dominating set problem. Further, we consider both the power dominating set problem - a special dominating set problem for sensor placement in power systems - and its connected version. We propose formulations and algorithms to solve these integer programs, and report results for several power system graphs. © 2012 Springer-Verlag.