Abstract

Dominating set problems are among the most important class of combinatorial problems in graph optimization, from a theoretical as well as from a practical point of view. In this paper, we address the recently introduced (minimum) weighted total domination problem. In this problem, we are given an undirected graph with a vertex weight function and an edge weight function. The goal is to find a total dominating set D with minimal weight. A total dominating set D isa subset of the vertices such that every vertex in the graph, including vertices in D, is adjacent to a vertex in D. The weight is measured by the sum of all vertex weights and edges weights in the subgraph induced by D, plus for each vertex not in D the minimum weight of an edge from such a vertex outside D to a vertex in D.