|
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 2-edge connected (resp. 2-node connected) for G if GW is 2-edge-connected (resp. 2-node-connected), 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
2-Connected Dominating Set Problem is to find a 2-connected dominating set W of minimum cardinality. Applications involving minimum connected dominating sets can be found in the design of ad-hoc wireless sensor networks, in the design of defense strategies against the attack of worms in peer-to-peer networks, in the design of fiber optics networks where regenerators of information may be required at some network vertices, and as models to investigate protein-protein 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 2-connected is a natural next step to take. In this presentation, we will describe three mixed integer programming formulations, valid inequalities, a primal heuristic, and Branch-and-Cut algorithms for the M2CDSP, in its 2-edge and 2-node connected variants.
|
