Back to Search
Start Over
Approximation algorithm for (connected) Italian dominating function.
- Source :
-
Discrete Applied Mathematics . Dec2023, Vol. 341, p169-179. 11p. - Publication Year :
- 2023
-
Abstract
- For a connected graph G = (V , E) , a function r i : V ↦ { 0 , 1 , 2 } is an Italian dominating function (IDF) if every vertex v with r i (v) = 0 is either adjacent to a vertex u with r i (u) = 2 or adjacent to at least two vertices x , y with r i (x) = r i (y) = 1. The weight of r i is ∑ v ∈ V r i (v) and the minimum Italian dominating function problem (MinIDF) is to compute an IDF with minimum weight. The minimum connected Italian dominating function problem (MinCIDF) is to find a minimum weight IDF r c i such that the subgraph of G induced by vertex set { v ∈ V ∣ r c i (v) = 1 or r c i (v) = 2 } is connected. In this paper, we give a greedy algorithm for the MinIDF problem with approximation ratio at most 2 + ln (1 2 Δ + 1) , and a greedy algorithm for the MinCIDF problem with approximation ratio at most 4 + ln (1 2 Δ − 1) , where Δ is the maximum degree of the graph. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GREEDY algorithms
*APPROXIMATION algorithms
*DOMINATING set
*GRAPH connectivity
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 341
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 173233549
- Full Text :
- https://doi.org/10.1016/j.dam.2023.08.006