Given a network graph \(G=(V,E)\) , a subset \(T\subseteq V\) is said to be a total dominating set (TDS) if every \(v\in V\) is adjacent to at least one node in T. In this paper, we first present a distributed algorithm for the minimum TDS problem via the LP relaxation techniques. For a positive integer k and maximum degree \(\Delta \) , the proposed algorithm outputs a fractional total dominating set of expected size \(O(k\Delta ^\frac{2}{k})|TDS_{OPT}|\) , where \(TDS_{OPT}\) is an optimal TDS. The distributed algorithm runs in \(O(k^2)\) communication rounds, and the algorithm uses messages of size \(O(\log \Delta )\) . Then we give a rounding algorithm. The fractional solution is rounded to obtain an integer total dominating set for the original problem.
