A survey on variant domination problems in geometric intersection graphs
A graph \(G=(V,E)\) is called a geometric intersection graph if there exists a set \(P\) of geometric objects and a bijection \(f:V\rightarrow P\) such that \(uv\in E\) if and only if \(f(u)\) and \(f(v)\) intersect. If \(P\) is a set of discs, then \(G\) is called a disc graph. Other types of geometric intersection graphs are unit disc graphs, rectangle graphs and unit square\Ngraphs. In this paper, the authors present a survey of complexity, algorithmic results, and approximation algorithm results for several variants of domination problems such as minimum domination problem, minimum connected domination problem, minimum total domination problem, minimum total restrained domination problem, minimum secure domination problem, minimum secure connected domination problem and minimum secure total domination problem in some geometric intersection graphs such as disc graphs, rectangle graphs, unit disc graphs, and circle graphs. Several open problems and directions for further research are presented in the concluding section.
- scientific article; zbMATH DE number 1161247
- scientific article; zbMATH DE number 1124601
- The algorithm and complexity of co-secure domination in geometric intersection graphs
- A survey of selected recent results on total domination in graphs
- The dominating set problem in geometric intersection graphs
- A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
- A new bound on maximum independent set and minimum connected dominating set in unit disk graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- A threshold of ln n for approximating set cover
- Algorithmic aspects of secure domination in unit disk graphs
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Approximation algorithms for connected dominating sets
- Approximation schemes for covering and packing problems in image processing and VLSI
- Approximation schemes for wireless networks
- APX-hardness of domination problems in circle graphs
- Dominating set of rectangles intersecting a straight line
- Domination in Geometric Intersection Graphs
- Edge intersection graphs of single bend paths on a grid
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Hamiltonian circuits in interval graph generalizations
- scientific article; zbMATH DE number 3827200 (Why is no real title available?)
- scientific article; zbMATH DE number 2188604 (Why is no real title available?)
- scientific article; zbMATH DE number 2209525 (Why is no real title available?)
- Improving construction for connected dominating set with Steiner tree in wireless sensor networks
- Independent set of intersection graphs of convex objects in 2D
- Label placement by maximum independent set in rectangles
- Minimum connected dominating sets and maximal independent sets in unit disk graphs
- On bounding the chromatic number of L-graphs
- On connected domination in unit ball graphs
- On dominating set of some subclasses of string graphs
- On grounded -graphs and their relatives
- On total restrained domination in graphs
- Orthogonal segment stabbing
- 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 total domination in graphs
- Simple heuristics for unit disk graphs
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- The complexity of domination problems in circle graphs
- Tighter approximation bounds for minimum CDS in wireless ad hoc networks
- Unit disk graph recognition is NP-hard
- Unit disk graphs
- Vertex Intersection Graphs of Paths on a Grid
This page was built for publication: A survey on variant domination problems in geometric intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6536206)
