An O(² n)-approximation algorithm for 2-edge-connected dominating set
Belgi, Amir · Nutov, Zeev
Original · EN
In the Connected Dominating Set problem we are given a graph G=(V,E) and seek a minimum size dominating set S V such that the subgraph G[S] of G induced by S is connected. In the 2-Edge-Connected Dominating Set problem G[S] should be 2-edge-connected. We give the first non-trivial approximation algorithm for this problem, with expected approximation ratio O(²n).
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.