ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS

DOI10.1142/S1793830910000504zbMath1209.68652MaRDI QIDQ3560065

Xiao-Dong Hu, Xiumei Wang, Wei-Ping Shang

Publication date: 19 May 2010

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmunit disk graphdominating

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (8)

Domination parameters with number 2: interrelations and algorithmic consequences ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Binary programming formulations for the upper domination problem ⋮ Approximation algorithm for (connected) Italian dominating function ⋮ Roman domination and independent Roman domination on graphs with maximum degree three ⋮ ON THE ROMAN BONDAGE NUMBER OF A GRAPH ⋮ Approximation algorithm for a generalized Roman domination problem in unit ball graphs ⋮ Nearly tight approximation algorithm for (connected) Roman dominating set

Cites Work

• Unit disk graphs
• Roman domination in graphs.
• Defending the Roman Empire---a new strategy
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A characterization of Roman trees
• Simple heuristics for unit disk graphs

This page was built for publication: ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS