The Study On The Fault-tolerant Outer-connected Dominating Set Problems Based On Greedy Algorithms

Given a graph G and a positive integer m,let C be a subset of the vertex set V,if every vertex in V\C is adjacent to at least m vertices in C and the subgraph of G induced by V\C is connected,then C is called an m-fold outer-connected dominating set of G.If a vertex subset C is an m-fold outer-connected dominating set and the subgraph of G induced by C has no isolated,then C is called an m-fold total outer-connected dominating set of G.This paper studies the problems of m-fold outer-connected dominating set and m-fold total outer-connected dominating set on a general graph,presents greedy algorithms based on potential functions respectively,and proves the proposed algorithms approximate ratios to be α+1+ln(Δ+m+1)and β+3+ln(Δ+m)respectively,whereΔ is the maximum degree of the graph,α is a positive number at most Δ+m+1,and βis a positive number at most Δ+m+2.