J. Schleich, Le Thi H.A, Bouvry P.: "Solving the Minimum m-Dominating Set problem by a Continuous Optimization Approach based on DC Programming and DCA".

Abstract:  We propose a new optimization approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) to the so-called Minimum M-Dominating Set problem in graphs. This problem is beforehand re-casted as a polyhedral DC program with the help of exact penalty in DC programming. The related DCA is original and computer efficient because it consists of solving a few linear programs and converges after a finite number of iterations to an integer solution while working in a continuous domain. Numerical simulations show the efficiency and robustness of DCA and its superiority with respect to standard methods.

 
Keyword(s):  DC programming and DCA ; Exact penalty ; Minimum dominating set.
 
Citation: J. Schleich, Le Thi H.A, Bouvry P., Solving the Minimum m-Dominating Set problem by a Continuous Optimization Approach based on DC Programming and DCA, Journal of Combinatorial Optimization, 24(4): 397-412 (2012).
 
Download link