Algorithmes heuristiques et exacts pour le problème de l’ensemble dominant connexe minimum
In this work, we address the minimum connected dominating set problem. We focus, in particular, on the development of solution methods based on constraint programming and integer programming, including one heuristic and some exact methods that can be used as heuristics if we limit their running time. These are based on Benders decomposition and exploit a stand-alone and an iterative probing strategy. In particular, we develop a method based on the stand-alone Benders decomposition, another combining this one with an iterative probing strategy, a variant of the latter using constraint programming, and finally, a method using only constraint programming. Experimental results show that these methods are effecient, since they perform better than those known in the literature. In particular, iterative probing Benders decomposition provides the best results overall.
Connected dominating set Benders decomposition Iterative probing Constraint programming Integer programming