Approximating domination on intersection graphs of paths on a grid

DOI10.1007/978-3-319-89441-6_7zbMath1504.68179OpenAlexW2795353754MaRDI QIDQ1644927

Saeed Mehrabi

Publication date: 22 June 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-89441-6_7

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

On dominating set of some subclasses of string graphs ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Approximability of covering cells with line segments ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames

This page was built for publication: Approximating domination on intersection graphs of paths on a grid