Abstract

Let G = (V,E) be a connected undirected graph with a set of vertices V and a set of edges E. For a given W V , let W V be the subset of vertices of V formed by W and those vertices that share an edge with a vertex of W. If W = V holds, W is called a dominating set of G. Furthermore, denoting by E(W) = {{i, j} 2 E : i, j 2 W} the subset of edges of G with both end vertices in W, let GW = (W,E(W)) be the subgraph W induces in G. A dominating set W is 2edge connected (resp. 2node connected) for G if GW is 2edgeconnected (resp. 2nodeconnected), i.e., if for every pair of distinct vertices u, v 2 W there exists two edge (resp. node) disjoint paths in GW connecting them. The Minimum
2Connected Dominating Set Problem is to find a 2connected dominating set W of minimum cardinality. Applications involving minimum connected dominating sets can be found in the design of adhoc wireless sensor networks, in the design of defense strategies against the attack of worms in peertopeer networks, in the design of fiber optics networks where regenerators of information may be required at some network vertices, and as models to investigate proteinprotein interactions. Reliability is
frequently a key issue in the design of some of these networks, particularly for telecommunications. When that applies, requiring that the dominating sets be 2connected is a natural next step to take. In this presentation, we will describe three mixed integer programming formulations, valid inequalities, a primal heuristic, and BranchandCut algorithms for the M2CDSP, in its 2edge and 2node connected variants.
