Approximating domination on intersection graphs of paths on a grid

DOI10.1007/978-3-319-89441-6_7MaRDI QIDQ1644927zbMATH OpenOpenAlexFDO

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

Recommendations

• On dominating set of some subclasses of string graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Approximation algorithms for \(B _{1}\)-EPG graphs
• On independent set on B1-EPG graphs

Cited in

(7)

• On dominating set of some subclasses of string graphs
• Approximating minimum dominating set on string graphs
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• scientific article; zbMATH DE number 4057564 (Why is no real title available?)
• Approximating dominating set on intersection graphs of rectangles and L-frames
• On approximating MIS over B1-VPG graphs*
• Computing maximum independent set on outerstring graphs and their relatives

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

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