Approximation algorithm for (connected) Italian dominating function

DOI10.1016/j.dam.2023.08.006zbMath1526.05109OpenAlexW4386268994MaRDI QIDQ6090069

Zhao Zhang, Ke Li

Publication date: 13 November 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2023.08.006

zbMATH Keywords

greedy algorithmapproximation ratioItalian dominating functionnon-submodular optimizationconnected Italian dominating function

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Connectivity (05C40)

Cites Work

• Unnamed Item
• Roman \(\{2 \}\)-domination
• Italian domination in trees
• Design and analysis of approximation algorithms
• Roman domination in graphs.
• Italian domination of Cartesian products of directed cycles
• Algorithmic aspects of Roman domination in graphs
• Nearly tight approximation algorithm for (connected) Roman dominating set
• Roman \(\{2\}\)-domination problem in graphs
• A new upper bound for the perfect Italian domination number of a tree
• Italian domination in rooted product graphs
• Approximation algorithm for a generalized Roman domination problem in unit ball graphs
• Varieties of Roman Domination
• ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
• Italian domination and perfect Italian domination on Sierpiński graphs
• Algorithmic aspects of total Roman ${2}$-domination in graphs

This page was built for publication: Approximation algorithm for (connected) Italian dominating function