Solving the connected dominating set problem and power dominating set problem by integer programming
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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.