Weighted k-domination problem in fuzzy networks

In real-life scenarios, both the vertex weight and edge weight in a network are hard to define exactly. We can incorporate the fuzziness into a network to handle this type of uncertain situation. Here, we use triangular fuzzy number to describe the vertex weight and edge weight of a fuzzy network G . In this paper, we consider weighted k -domination problem in fuzzy networks. The weighted k -domination (WKD) problem is to find a k dominating set D which minimizes the cost $f(D):=\sum_{u\in D}w(u)+\sum_{v\in V\setminus D}\min\{\sum_{u\in S}w(uv)|S\subseteq N(v)\cap D, |S|=k\}$. First, we put forward an integer linear programming model with a polynomial number of constrains for the WKD problem. If G is a cycle, we design a dynamic algorithm to determine its exact weighted 2 -domination number. If G is a tree, we give a label algorithm to determine its exact weighted 2 -domination number. Combining a primal-dual method and a greedy method, we put forward an approximation algorithm for general fuzzy network on the WKD problem. Finally, we describe an application of the WKD problem to police camp problems.2010 Mathematics Subject Classification. 05C69, 05C35, 03E72