The algorithm and complexity of secure domination in 3-dimensional box graphs

DOI10.1016/J.DAM.2025.01.018MaRDI QIDQ7021397zbMATH OpenFDO

Authors Cai-Xia Wang, Yu Yang, S. J. Xu

Publication date 28 February 2025

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

Full work available at URL https://doi.org/10.1016/J.DAM.2025.01.018

zbMATH Keywords

APX-hardnessbox graphPTASsecure dominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamic programming (90C39)

Cites work

• Algorithmic aspects of secure domination in unit disk graphs
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Approximation schemes for covering and packing problems in image processing and VLSI
• Dominating set of rectangles intersecting a straight line
• Hamiltonian circuits in interval graph generalizations
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• Independent set of intersection graphs of convex objects in 2D
• Label placement by maximum independent set in rectangles
• On computing a minimum secure dominating set in block graphs
• On secure domination in graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
• Secure domination in cographs
• Secure domination in proper interval graphs
• Some APX-completeness results for cubic graphs
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• The complexity of secure domination problem in graphs
• The secure domination problem in cographs
• Two algorithms for secure graph domination

This page was built for publication: The algorithm and complexity of secure domination in 3-dimensional box graphs

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