Abstract
We consider the minimum connected dominating set problem. We present an integer programming formulation and new valid inequalities. A branch-and-cut algorithm based on the reinforced formulation is also provided. Computational results indicate that the reinforced lower bounds are always stronger than the bounds implied by the formulation from which resulted one of the best known exact algorithms for the problem. In some cases, the reinforced lower bounds are stronger than those implied by the strongest known formulation to date. For dense graphs, our algorithm provides the best results in the literature. For sparse instances, known to be harder, our method is outperformed by another one. We discuss reasons for that and how to improve our current computational results. One possible way to achieve such goals is to devise specific separation algorithms for some classes of valid inequalities introduced here.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Balasundaram, B., Butenko, S.: Graph domination, coloring and cliques in telecommunications. In: Handbook of Optimization in Telecommunications, pp. 865–890. Springer, Heidelberg (2006)
Borndörfer, R.: Aspects of Set Packing, Partitioning and Covering. Ph.D. thesis, Konrad-Zuse-Zentrum fur Informationstechnik, Berlin (1998)
Chen, S., Ljubić, I., Raghavan, S.: The regenerator location problem. Networks 55(3), 205–220 (2010)
Fujie, T.: The Maximum-leaf Spanning Tree Problem: formulations and facets. Networks 43(4), 212–223 (2004)
Fujie, T.: An exact algorithm for the Maximum-leaf Spanning Tree Problem. European Journal of Operational Research 104, 250–261 (2003)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)
Kruskal, J.: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7, 48–50 (1956)
Lucena, A., Maculan, N., Simonetti, L.: Reformulation and solution algorithms for the maximum leaf spanning tree problem. Computational Management Science 7, 289–311 (2010)
Magnanti, T.L., Wolsey, L.: Optimal Trees. In: Ball, O., et al. (eds.) Handbooks in OR and MS, vol. 7, pp. 503–615. North-Holland, Amsterdam (1995)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disc graphs. Networks 25, 59–68 (1995)
Padberg, M.W., Rinaldi, G.: A Branch-and-Cut algorithm for resolution of large scale of Symmetric Traveling Salesman Problem. SIAM Review 33, 60–100 (1991)
Padberg, M.W., Wolsey, L.: Trees and cuts. Annals of Discrete Mathematics 17, 511–517 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Simonetti, L., Salles da Cunha, A., Lucena, A. (2011). The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm. In: Pahl, J., Reiners, T., Voß, S. (eds) Network Optimization. INOC 2011. Lecture Notes in Computer Science, vol 6701. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21527-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-21527-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21526-1
Online ISBN: 978-3-642-21527-8
eBook Packages: Computer ScienceComputer Science (R0)