Approximation for minimum total dominating set
Junmin Zhu · 2009
A total dominating set is a dominating set which induces a subgraph without isolated vertices. In this paper, we study the approximation of minimum total dominating set problem. First, we present a new analysis for one-step greedy algorithm with approximation ratio ln(δ-0.5)+1.5, where δ is the maximum degree of the given graph. Second, we prove some approximation hardness of this problem on various classes of graphs, including sparse graphs, small degree graphs, directed graphs, etc.