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

DOI10.1007/S10878-019-00459-1MaRDI QIDQ2292134zbMATHOpenAlexWikidataFDO

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

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)

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

(3)

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

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)