Back to Search
Start Over
On dominating set of some subclasses of string graphs.
- Source :
-
Computational Geometry . Dec2022, Vol. 107, pN.PAG-N.PAG. 1p. - Publication Year :
- 2022
-
Abstract
- We provide constant factor approximation algorithms for the Minimum Dominating Set (MDS) problem on several subclasses of string graphs i.e. intersection graphs of simple curves on the plane. For k ≥ 0 , unit B k -VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. We give an 18-approximation algorithm for the MDS problem on unit B 0 -VPG graphs. This partially addresses a question of Katz et al. (2005) [24]. We also give an O (k 4) -approximation algorithm for the MDS problem on unit B k -VPG graphs. We show that there is an 8-approximation algorithm for the MDS problem on vertically-stabbed L -graphs. We also give a 656-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs. This is the first constant-factor approximation algorithm for the MDS problem on stabbed rectangle overlap graphs and extends a result of Bandyapadhyay et al. (2019) [31]. We prove some hardness results to complement the above results. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09257721
- Volume :
- 107
- Database :
- Academic Search Index
- Journal :
- Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 157301067
- Full Text :
- https://doi.org/10.1016/j.comgeo.2022.101884