Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA

DC programming and DCA; Exact penalty; Minimum dominating set; Continuous domain; Continuous optimization; D-C programming; DC algorithm; Exact penalties; Finite number; Integer solutions; Linear programs; Optimization approach; Set problems; Standard method; Computer Science Applications; Discrete Mathematics and Combinatorics; Control and Optimization; Computational Theory and Mathematics; Applied Mathematics

Abstract :

[en] 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. © Springer Science+Business Media, LLC 2011.

Disciplines :

Computer science

Author, co-author :

SCHLEICH, Julien ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

An Le Thi, Hoai; LITA, University Paul Verlaine-Metz, 57045 Metz, France

BOUVRY, Pascal ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

External co-authors :

yes

Language :

English

Title :

Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA

Publication date :

November 2012

Journal title :

Journal of Combinatorial Optimization

ISSN :

1382-6905

eISSN :

1573-2886

Publisher :

Springer Science and Business Media LLC

Volume :

Issue :

Pages :

397 - 412

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

http://link.springer.com/content/pdf/10.1007/s10878-011-9396-0.pdf

Available on ORBilu :

since 21 November 2023

Statistics

Number of views

7 (0 by Unilu)

Number of downloads

0 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

WoS citations^™

Bibliography

Basagni S, Mastrogiovanni M, Panconesi A, Petrioli C (2006) Localized protocols for ad hoc clustering and backbone formation: A performance comparison. IEEE Trans Parallel Distrib Syst 17(4):292- 306 (Pubitemid 43380046)
Brešar B, Henning MA, Rall DF (2008) Rainbow domination in graphs. Taiwan J Math 12:213-225
Dai D, Yu C (2009) A 5 + ε-approximation algorithm for minimum weighted dominating set in unit disk graph. Theor Comput Sci 410:756-765
Dai F, Wu J (2004) An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans Parallel Distrib Syst 15(10):908-920 (Pubitemid 40527339)
Dutot A, Guinand F, Olivier D, Pigné Y (2007) Graphstream: A tool for bridging the gap between complex systems and dynamic graphs. In: EPNACS: Emergent properties in natural and artificial complex systems
Erdo"s P, Rényi A (1959) On random graphs. Publ Math 6:290-297
Fomin FV, Kratsch D, Woeginger GJ (2005) Exact (exponential) algorithms for the dominating set problem. In: Graph-theoretic concepts in computer science. Lecture notes in computer science, vol 3353. Springer, Berlin, pp 245-256
Garey M, Johnson DS (1990) Computers and intractability; A guide to the theory of NP-completeness. Freeman, San Francisco
Gaspers S, Kratsch D, Liedloff M (2006) Exponential time algorithms for the minimum dominating set problem. In: Proceedings of SWAT, vol 4059, pp 148-159 (Pubitemid 44123966)
Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374-387 (Pubitemid 128664048)
Harary F, Haynes TW (2000) Double domination in graphs. Ars Comb 50:201-213
Hedetniemi ST, Laskar RC (1990) Bibliography on domination in graphs and some basic definitions of domination parameters. Discrete Math 86(1-3):257-277
Khamis SM, Daoud SS, Essa HAE (2009) A randomized algorithm for determining dominating set in graphs of maximum degree five. Theor Comput Sci 410:5122-5127
Le Thi HA, Pham Dinh T (1997) Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. J Glob Optim 11(3):253-285
Le Thi HA, Pham Dinh T (2003) Large scale molecular optimization from distances matrices by a dc optimization approach. SIAM J Optim 14(1):77-116
Le Thi HA, Pham Dihn T (2005) The dc (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res 133(1-4):23-46
Le Thi HA, Pham Dinh T, Le Dung M (1999) Exact penalty in DC programming. Vietnam J Math 27(2):169-178
Liao CS, Chang GJ (2003) k-tuple domination in graphs. Inf Process Lett 87(1):45-50
Liedloff M (2008) Finding a dominating set on bipartite graphs. Inf Process Lett 107:154-157
Pham Dinh T, Le Thi HA (1997) Convex analysis approach to DC programming: Theory algorithms and applications. Acta Math Vietnam 22(1):289-355
Pham Dinh Dinh T, Le Thi HA (1998) DC optimization algorithms for solving the trust region subproblem. SIAM J Optim 8:476-505
Sampathkumar E (1983) The global domination number of a graph. J Math Phys Sci 23(5):377-385
van Rooij JMM, Bodlaender HL (2008) Design by measure and conquer: A faster exact algorithm for dominating set. In: Proceedings of STACS, pp 657-668
Woeginger GJ (2003) Exact algorithms for NP-hard problems: A survey. In: Jünger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization - eureka! You shrink! LNCS, vol 2570. Springer, Berlin, pp 185-207 (Pubitemid 137631161)
Wu J, Li H (1999) On calculating connected dominating sets for efficient routing in ad hoc wireless networks. In: Proc third ACM int'l workshop discrete algorithms and methods for mobile computing and comm dial M, pp 7-17
Wu J, Cardei M, Dai F, Yang S (2005) Extended dominating set in ah hoc networks using cooperative communication. In: Networking. LNCS, vol 3462, pp 1393-1396 (Pubitemid 41312899)