Liar's dominating set problem on unit disk graphs

DOI10.1016/J.DAM.2020.01.017MaRDI QIDQ2201773zbMATH OpenOpenAlexFDO

Authors Ramesh K. Jallu, Gautam K. Das

Publication date 17 September 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.01.017

zbMATH Keywords

approximation algorithmdominating setunit disk graphliar's dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Liar's domination in 2D
• Liar's domination in unit disk graphs
• Liar's dominating set in unit disk graphs
• Algorithm and hardness results on liar's dominating set and \({k}\)-tuple dominating set
• Minimum dominating set problem for unit disks revisited

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A linear time algorithm for liar's domination problem in proper interval graphs
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Liar's dominating set in unit disk graphs
• Liar's dominating sets in graphs
• Liar's domination
• Liar's domination in graphs
• Liar's domination in graphs: complexity and algorithm
• \(k\)-tuple domination in graphs

Cited in

(6)

• Liar's domination in unit disk graphs
• Liar's domination in 2D
• Dominating set of rectangles intersecting a straight line
• Algorithm and hardness results on liar's dominating set and \({k}\)-tuple dominating set
• Algorithmic aspects of secure domination in unit disk graphs
• Liar's dominating sets in graphs

This page was built for publication: Liar's dominating set problem on unit disk graphs

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