Approximation algorithm for connected Roman k-dominating set

DOI10.1016/J.JCSS.2026.103773MaRDI QIDQ7239831zbMATH OpenFDO

Authors Mengmeng He, Ralf Klasing, Yaping Mao, Xiaoyan Zhang

Publication date 8 May 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2026.103773

zbMATH Keywords

approximation ratioconnected Roman \(k\)-dominating setgreedy algorithmnon-submodularRoman \(k\)-dominating set

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• Algorithmic aspects of Roman domination in graphs
• Approximation algorithm for a generalized Roman domination problem in unit ball graphs
• Double vertex-edge domination in graphs: complexity and algorithms
• Nearly tight approximation algorithm for (connected) Roman dominating set
• Roman \(k\)-domination: hardness, approximation and parameterized results
• Roman domination in graphs.
• Roman domination on strongly chordal graphs
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
• Weakly connected Roman domination in graphs

This page was built for publication: Approximation algorithm for connected Roman \(k\)-dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7239831)