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

DOI10.1007/S10878-019-00459-1zbMATH Open1434.05117OpenAlexW2981943715WikidataQ126985614 ScholiaQ126985614MaRDI QIDQ2292134FDOQ2292134

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

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

zbMATH Keywords

unit ball graphconnected strong \(k\)-Roman dominating setconstant approximation algorithm

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Approximation algorithm for the minimum partial connected Roman dominating set problem
• Approximation algorithm for (connected) Italian dominating function
• Nearly tight approximation algorithm for (connected) Roman 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)