Back to Search
Start Over
Weighted k-domination problem in fuzzy networks.
- Source :
-
Journal of Intelligent & Fuzzy Systems . 2023, Vol. 44 Issue 5, p7643-7651. 9p. - Publication Year :
- 2023
-
Abstract
- 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 network. The weighted k-domination (WKD) problem is to find a k dominating set D which minimizes the cost f (D) : = ∑u∈Dw (u) + ∑v∈V\D min {∑u∈Sw (uv) |S ⊆ N (v) ∩ 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 problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10641246
- Volume :
- 44
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- Journal of Intelligent & Fuzzy Systems
- Publication Type :
- Academic Journal
- Accession number :
- 164007955
- Full Text :
- https://doi.org/10.3233/JIFS-213120