Nearly tight approximation algorithm for (connected) Roman dominating set
From MaRDI portal
Publication:2080821
DOI10.1007/s11590-022-01862-0zbMath1503.90150OpenAlexW4220784935MaRDI QIDQ2080821
Ding-Zhu Du, Ke Li, Zhao Zhang, Yingli Ran
Publication date: 11 October 2022
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11590-022-01862-0
greedy algorithmnon-submodular optimizationapproxiamtion ratioconnected Roman dominating setRoman dominating set
Related Items (1)
Cites Work
- Roman domination on strongly chordal graphs
- On the roman domination in the lexicographic product of graphs
- Design and analysis of approximation algorithms
- Roman domination in regular graphs
- Roman domination in graphs.
- An analysis of the greedy algorithm for the submodular set covering problem
- Algorithmic aspects of Roman domination in graphs
- Double vertex-edge domination in graphs: complexity and algorithms
- Approximation algorithm for a generalized Roman domination problem in unit ball graphs
- Weakly connected Roman domination in graphs
- Roman domination number on cardinal product of paths and cycles
- ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
- Extremal Problems for Roman Domination
- Graph-Theoretic Concepts in Computer Science
- Unnamed Item
This page was built for publication: Nearly tight approximation algorithm for (connected) Roman dominating set
