Find in Library

In this paper, we consider a variant of dominating set problem, i.e., the total dominating set problem. Given an undirected graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula>, a subset of vertices <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>T</mi><mo>⊆</mo><mi>V</mi></mrow></semantics></math></inline-formula> is called a total dominating set if every vertex in <i>V</i> is adjacent to at least one vertex in <i>T</i>. Based on LP relaxation techniques, this paper gives a distributed approximation algorithm for the total dominating set problem in general graphs. The presented algorithm obtains a fractional total dominating set that is, at most, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo>+</mo><msup><mo>Δ</mo><mfrac><mn>1</mn><mi>k</mi></mfrac></msup><mo stretchy="false">)</mo></mrow><msup><mo>Δ</mo><mfrac><mn>1</mn><mi>k</mi></mfrac></msup></mrow></semantics></math></inline-formula> times the size of the optimal solution to this problem, where <i>k</i> is a positive integer and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Δ</mo></semantics></math></inline-formula> is the maximum degree of <i>G</i>. The running time of this algorithm is constant communication rounds under the assumption of a synchronous communication model.