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

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 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 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 Erdő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 Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374–387 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 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