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)

Review text

Let \(G=(V,E)\) be a simple graph. A secure dominating set of \(G\) is a set \(S \subseteq V\) with the property that for each \(u \in V\setminus S\), there exists \(v \in S\) adjacent to \(u\) such that \((S\cup \{u\})\setminus \{v\}\) is a dominating set of graph \(G\). The main objective of this article is to determine the minimum secure dominating set (MSDS) for a certain class of geometric intersection graphs.\N \par To achieve their aim, three stages are used in their methodology. In stage one, the authors prove that the MSDS problem is APX-hard in \(d\)-box graphs for any fixed integer \(d \geq 2\). In stage two, they obtain a PTAS for the MSDS problem which achieves an \((1+\frac{2l}{k})\)-approximation and runs in \(n^{O(K^3)}\) time for unit cube graphs and an \((1+\frac{6}{k})\)-approximation and runs in \(n^{O(k^2)}\) time for unit ball graphs. In stage three, they provide a dynamic programming algorithm that improves the results obtained in stage two.

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)