Approximation algorithm for a generalized Roman domination problem in unit ball graphs

DOI10.1007/S10878-019-00459-1MaRDI QIDQ2292134zbMATH OpenOpenAlexWikidataFDO

Authors Yalin Shi, Zhao Zhang, Zan-Bo Zhang, Xiaoyan Zhang, Limin Wang

Publication date 3 February 2020

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-019-00459-1

zbMATH Keywords

connected strong \(k\)-Roman dominating setconstant approximation algorithmunit ball graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Programming involving graphs or networks (90C35)

Recommendations

• ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
• On connected domination in unit ball graphs
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• Algorithmic aspects of Roman domination in graphs
• Algorithms for the minimum weight k-fold (connected) dominating set problem

Cites work

• Defending the Roman Empire from multiple attacks
• Defending the Roman Empire---a new strategy
• Extremal problems for roman domination
• Extremal problems on weak Roman domination number
• Graph-Theoretic Concepts in Computer Science
• ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
• Roman domination in graphs.
• Roman domination on 2-connected graphs

Cited in

(4)

• Nearly tight approximation algorithm for (connected) Roman dominating set
• Approximation algorithm for (connected) Italian dominating function
• Approximation algorithm for the minimum partial connected Roman dominating set problem
• Approximation algorithm for connected Roman k-dominating set

This page was built for publication: Approximation algorithm for a generalized Roman domination problem in unit ball graphs

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