Total Domination in Weighted Cactus Graph

A dominating set of a graph G = (V ,E) is a subset S in V if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is said to be a total dominating set if every vertex is adjacent to a vertex in S. The total domination problem is to find a minimum size of a total dominating set of a graph. In addition, suppose that every vertex v belongs to V is associated with a weight w(v). The weight total domination problem is to find a total dominating set S such that its total weight W(S) = Σ{w(v) : v is in S} is minimum. In this paper, we provide a dyanmic programming algorithm for the weight total domination problem on cactus graphs. The time complexity of this algorithm is O(m + n).