Abstract
Given an undirected graph G = (V, E), a subset W of V is a dominating set of G  if, for every vertex i ∈ V\W, there exists an edge  e = [i,j] ∈ E  with j ∈W. The dominating set is connected if the subgraph it induces in G is connected. Accordingly, the Minimum Connected Dominating Set Problem (MCDSP) is to find a connected dominating set with as few vertices as possible. MCDSP and the very closely related Maximum Leaf Spanning Tree Problem (MLSTP) have been suggested in the literature as a model to, among others, ad-hoc wireless networks and fiber optics networks where regenerators of information must be used. In our presentation we emphasize the close links that exist between MCDSP and MLSTP and review the applications suggested for the two problems. We also present a new formulation for MCDSP, valid inequalities to strengthen it and an associated branch-and-cut algorithm. Computational results are presented, showing that this algorithm is competitive with the best exact solution algorithms available for MCDSP and MLSTP.

Autores
Abilio Lucena
Universidade Federal do Rio de Janeiro
abiliolucena@globo.com

Alexandre Salles da Cunha
Universidade Federal de Minas Gerais
acunha@dcc.ufmg.br

Luidi Simonetti
Universidade Federal Fluminense
lsimonetti@gmail.com