A greedy algorithm for the fault-tolerant outer-connected dominating set problem (Q2025101)

In this paper, the authors generalize the known outer-connected dominating set (OCSD) problem to the fault-tolerant OCDS problem. A vertex subset \(C\) of a graph \(G=(V,E)\) is an \(m\)-fold outer-connected dominating set (\(m\)-fold OCDS), if every vertex in \(V\setminus C\) has at least \(m\)-neighbors in \(C\) and the subgraph of \(G\) induced by \(V\setminus C\) is connected. The minimum \(m\)-fold OCDS problem of a graph \(G\) is to find an \(m\)-fold OCDS of minimum cardinality. The authors present a greedy algorithm for this problem and show that the approximation ratio is at most \(\alpha+1+\ln(\Delta+m +1)\), where \(\Delta\) is the maximum degree of the graph and \(\alpha\) is a positive number at most \(\Delta+m+1\).