ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS

DOI10.1142/S1793830910000504MaRDI QIDQ3560065zbMATH OpenFDO

Authors Xiumei Wang, Xiaodong Hu, Weiping Shang

Publication date 19 May 2010

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

Full work available at URL https://doi.org/10.1142/S1793830910000504

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)

Recommendations

• Roman domination in unicyclic graphs
• Roman domination in graphs
• A note on Roman domination in graphs
• A note on Roman domination in graphs
• Roman domination in regular graphs
• On total Roman domination in graphs
• Roman \(k\)-domination in graphs
• On the Roman domination stable graphs
• Roman lict domination in graphs

Cites work

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

Cited in

(14)

• Approximation algorithm for the minimum partial connected Roman dominating set problem
• The signed (total) Roman domination problem on some classes of planar graphs -- convex polytopes
• Bisectored unit disk graphs
• Minimal Roman dominating functions: extensions and enumeration
• Perfect Roman domination: aspects of enumeration and parameterization
• Binary programming formulations for the upper domination problem
• Domination parameters with number 2: interrelations and algorithmic consequences
• Approximation algorithm for (connected) Italian dominating function
• Nearly tight approximation algorithm for (connected) Roman dominating set
• Total Roman domination and total domination in unit disk graphs
• Minimal Roman dominating functions: extensions and enumeration
• Approximation algorithm for a generalized Roman domination problem in unit ball graphs
• Roman domination and independent Roman domination on graphs with maximum degree three
• On the Roman bondage number of a graph

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

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