Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem

References

• Asavathiratham C, Roy S, Lesieutre B, Verghese G (2001) The influence model. IEEE Control Systems 21(6):52–64.Crossref, Google Scholar
• Balasundaram B, Butenko S (2006) Graph domination, coloring and cliques in telecommunications. Handbook of Optimization in Telecommunication (Springer, New York), 865–890.Crossref, Google Scholar
• Berge C (1973) Graphs and Hypergraphs (North Holland, Amsterdam).Google Scholar
• Borndörfer R (1998) Aspects of set packing, partitioning and covering. Ph.D. thesis, Konrad-Zuse-Zentrum fur Informationstechnik, Berlin.Google Scholar
• Chen S, Ljubić I, Raghavan S (2010) The regenerator location problem. Networks 55(3):205–220.Crossref, Google Scholar
• Chopra S, Rao MR (1994a) The Steiner tree problem I: Formulations, compositions and extensions of facets. Math. Programming 64(1–3):209–229.Crossref, Google Scholar
• Chopra S, Rao MR (1994b) The Steiner tree problem II: Properties and classes of facets. Math. Programming 64(1–3):231–246.Crossref, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders' cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Cooper C, Klasing R, Zito M (2005) Lower bounds and algorithms for dominating sets in Web graphs. Internet Math. 2(3):275–300.Crossref, Google Scholar
• Domingos P, Richardson M (2001) Mining the network value of customers. Proc. Seventh Internat. Conf. Knowledge Discovery Data Mining (ACM, New York).Crossref, Google Scholar
• Eubank S, Guclu H, Kumar VSA, Marathe MV, Srinivasan A, Toroczkai Z, Wang N (2004) Modelling disease outbreaks in realistic urban social networks. Nature 429(6988):180–184.Crossref, Google Scholar
• Fan N, Watson JP (2012) Solving the connected dominating set problem and power dominating set problem by integer programming. Combinatorial Optimization and Applications, Lecture Notes in Computer Science, Vol. 7402 (Springer, Berlin), 371–383.Crossref, Google Scholar
• Fernau H, Kneis J, Kratsch D, Langer A, Liedlo M, Raible D, Rossmanith P (2011) An exact algorithm for the maximum leaf spanning tree problem. Theor. Comput. Sci. 412(45):6290–6302.Crossref, Google Scholar
• Fujie T (2003) An exact algorithm for the maximum leaf spanning tree problem. Comput. Oper. Res. 30(13):1931–1944.Crossref, Google Scholar
• Fujie T (2004) The maximum-leaf spanning tree problem: Formulations and facets. Networks 43(4):212–223.Crossref, Google Scholar
• Goldenberg J, Libai B, Muller E (2001) Using complex systems analysis to advance marketing theory development. Acad. Marketing Sci. Rev. 9:1–19.Google Scholar
• Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374–387.Crossref, Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based Benders decomposition. Math. Programming 96(1):33–60.Crossref, Google Scholar
• Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. P. Amer. Math. Soc. 7:48–50.Crossref, Google Scholar
• Liu CL (1968) Introduction to Combinatorial Mathematics (McGraw-Hill, New York).Google Scholar
• Lucena A, Maculan N, Simonetti L (2010) Reformulation and solution algorithms for the maximum leaf spanning tree problem. Comput. Management Sci. 7(3):289–311.Crossref, Google Scholar
• Marathe MV, Breu H, Hunt III HB, Ravi SS, Rosenkrantz DJ (1995) Simple heuristics for unit disc graphs. Networks 25(2):59–68.Google Scholar
• Martin RK (1991) Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10:119–128.Crossref, Google Scholar
• Milenković T, Memišević V, Bonato A, Pržulj N (2011) Dominating biological networks. PLOS ONE 6(8).Crossref, Google Scholar
• Padberg MW, Wolsey L (1983) Trees and cuts. Ann. Discrete Math. 17:511–517.Google Scholar
• Rogers EM (2003) Diffusion of Innovations (Free Press, New York).Google Scholar
• Simonetti L, da Cunha AS, Lucena A (2011) The minimum connected dominating set problem: Formulation, valid inequalities and branch-and-cut algorithm. Pahl J, Reiners T, Voβ S, eds. Network Optim.—Proc. 5th Internat. Network Optim. Conf., Hamburg, Lecture Notes in Computer Science, Vol. 6701 (Springer, Berlin), 162–169.Crossref, Google Scholar
• Stanley EA (2006) Social networks and mathematical modelling. Connections 27(1):43–49.Google Scholar
• Valente T (1995) Network Models of the Diffusion of Innovations (Hampton Press, Cresskill, NJ).Google Scholar
• Wang F, Du H, Camachoa E, Xua K, Lee W, Shi Y, Shan S (2011) On positive influence dominating sets in social networks. Theoret. Comput. Sci. 412(3):265–269.Crossref, Google Scholar
• Xie L, Zhu S (2007) A feasibility study on defending against ultra-fast topological worms. Proc. Seventh IEEE Internat. Conf. Peer-to-Peer Comput. (P2P'07) (IEEE, Piscataway), 61–70.Crossref, Google Scholar