Integer linear programming models for the weighted total domination problem

摘要

A total dominating set of a graph G=(V,E) is a subset D of V such that every vertex in V (including the vertices from D) has at least one neighbour in D. Suppose that every vertex v ∈ V has an integer weight w(v) ≥ 0 and every edge e ∈ E has an integer weight w(e) ≥ 0. Then the weighted total domination (WTD) problem is to find a total dominating set D which minimizes the cost f(D):=∑u∈Dw(u)+∑e∈E[D]w(e)+∑v∈V∖Dmin{w(uv)|u∈N(v)∩D}. In this paper, we put forward three integer linear programming (ILP) models with a polynomial number of constraints, and present some numerical results implemented on random graphs for WTD problem.