On dominating set of some subclasses of string graphs

DOI10.1016/j.comgeo.2022.101884zbMath1496.05123OpenAlexW4224293990WikidataQ114195517 ScholiaQ114195517MaRDI QIDQ2144448

Sandip Das, Dibyayan Chakraborty, Joydeep Mukherjee

Publication date: 13 June 2022

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2022.101884

zbMATH Keywords

approximation algorithmdominating setstring graphgeometric intersection graph

Mathematics Subject Classification ID

Linear programming (90C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (1)

Recognizing geometric intersection graphs stabbed by a line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersection graphs of L-shapes and segments in the plane
• Max point-tolerance graphs
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Minimum vertex cover in rectangle graphs
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Orthogonal segment stabbing
• Approximation hardness of dominating set problems in bounded degree graphs
• APX-hardness of domination problems in circle graphs
• String graphs. II: Recognizing string graphs is NP-hard
• Unit disk graphs
• Permutation graphs: Connected domination and Steiner trees
• Intersection graphs of curves in the plane
• Approximating domination on intersection graphs of paths on a grid
• The complexity of dominating set in geometric intersection graphs
• On bounding the chromatic number of L-graphs
• Dominating set on overlap graphs of rectangles intersecting a line
• Approximating minimum dominating set on string graphs
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Effectiveness of local search for art gallery problems
• Coloring curves that cross a fixed curve
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Vertex Intersection Graphs of Paths on a Grid
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Minimum Dominating Set Problem for Unit Disks Revisited
• Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• Domination in permutation graphs
• Approximation algorithms for NP-complete problems on planar graphs
• A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
• Packing and Covering with Non-Piercing Regions
• Simple heuristics for unit disk graphs
• Parameterized Domination in Circle Graphs
• Domination in Geometric Intersection Graphs
• Topology of Thin Film RC Circuits
• Covering segments with unit squares
• Approximation and Online Algorithms
• Optimality program in segment and string graphs

This page was built for publication: On dominating set of some subclasses of string graphs