Approximating dominating set on intersection graphs of rectangles and L-frames

DOI10.1016/J.COMGEO.2019.04.004MaRDI QIDQ2331213zbMATH OpenOpenAlexFDO

Authors Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, Subhash Suri

Publication date 25 October 2019

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsAPX-hardnessgeometric intersection graphsminimum dominating setPTAS

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Approximating dominating set on intersection graphs of rectangles and L-frames
• Dominating set of rectangles intersecting a straight line
• On dominating set of some subclasses of string graphs
• Domination in Geometric Intersection Graphs
• On the hardness of some geometric optimization problems with rectangles

Cites work

• A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• An algorithm for the maximum weight independent set problem on outerstring graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Analytical approach to parallel repetition
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Approximating domination on intersection graphs of paths on a grid
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Approximation algorithms for maximum independent set of pseudo-disks
• APX-hardness of domination problems in circle graphs
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• Dominating set of rectangles intersecting a straight line
• Domination in Geometric Intersection Graphs
• Edge intersection graphs of single bend paths on a grid
• Edge-intersection graphs of grid paths: the bend-number
• Geometric dominating-set and set-cover via local-search
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Improved results on geometric hitting set problems
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Max point-tolerance graphs
• Minimum Edge Dominating Sets
• On the hardness of approximating minimum vertex cover
• Optimal binary space partitions for segments in the plane
• Optimization problems in multiple-interval graphs
• Packing and covering with non-piercing regions
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• The hardness of approximation of Euclidean k-means
• Vertex Intersection Graphs of Paths on a Grid

Cited in

(11)

• Dominating set of rectangles intersecting a straight line
• On dominating set of some subclasses of string graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG 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
• Approximating dominating set on intersection graphs of rectangles and L-frames
• Hyperideal-based intersection graphs
• A survey on variant domination problems in geometric intersection graphs
• On some geometric optimization problems with segments
• The algorithm and complexity of secure domination in 3-dimensional box graphs

This page was built for publication: Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames

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