An Õ(log^2 n)-approximation algorithm for 2-edge-connected dominating set

12/20/2019
by   Amir Belgi, et al.
0

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 Õ(log^2n).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset